☀️ 문제 링크
🌻 문제 간단한 설명
DFS, BFS를 통해서 그림의 개수를 구하고, 그림의 최댓값을 찾는 문제다.
⚡️ 풀이
🌝 전체 코드
DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int Y;
static int X;
static int count;
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
static String[][] map;
static boolean[][] isVisited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Y = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
map = new String[Y][X];
isVisited = new boolean[Y][X];
for (int i = 0; i < Y; i++) {
map[i] = br.readLine().split(" ");
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
count = 0;
if (!isVisited[i][j] && map[i][j].equals("1")) {
dfs(i, j);
answer.add(count);
}
}
}
Collections.sort(answer);
System.out.println(answer.size());
System.out.println(answer.size() == 0 ? 0 : answer.get(answer.size() - 1));
}
private static void dfs(int y, int x) {
isVisited[y][x] = true;
count++;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
continue;
}
if (!isVisited[ny][nx] && map[ny][nx].equals("1")) {
dfs(ny, nx);
}
}
}
}BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int Y;
static int X;
static int count;
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
static String[][] map;
static boolean[][] isVisited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Y = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
map = new String[Y][X];
isVisited = new boolean[Y][X];
for (int i = 0; i < Y; i++) {
map[i] = br.readLine().split(" ");
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
count = 0;
if (!isVisited[i][j] && map[i][j].equals("1")) {
bfs(i, j);
answer.add(count);
}
}
}
Collections.sort(answer);
System.out.println(answer.size());
System.out.println(answer.size() == 0 ? 0 : answer.get(answer.size() - 1));
}
private static void bfs(int y, int x) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(y, x));
isVisited[y][x] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();
count++;
for (int i = 0; i < 4; i++) {
int ny = point.y + dy[i];
int nx = point.x + dx[i];
if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
continue;
}
if (!isVisited[ny][nx] && map[ny][nx].equals("1")) {
queue.add(new Point(ny, nx));
isVisited[ny][nx] = true;
}
}
}
}
static class Point {
int y;
int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
}🌛 코드별 설명
- 값 입력받기, 배열 생성 부분은 생략
탐색시작
// 그림의 갯수를 넣을 리스트 생성
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
// 그림의 넓이를 초기화 작업
count = 0;
if (!isVisited[i][j] && map[i][j].equals("1")) {
bfs(i, j);
// 탐색이 끝나면 count = 연결된 그림의 넓이이므로 답에 추가
answer.add(count);
}
}
}// BFS
private static void bfs(int y, int x) {
Queue<Point> queue = new LinkedList<>();
// 시작 지점 삽입
queue.add(new Point(y, x));
// 방문 체크
isVisited[y][x] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();
// 그림의 넓이++;
count++;
for (int i = 0; i < 4; i++) {
// 현위치에서 상하좌우 좌표
int ny = point.y + dy[i];
int nx = point.x + dx[i];
// map, isVisited의 값을 넘지않는지 체크
if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
continue;
}
// 방문하지 않았고, 그림이 연결되어있으면 탐색영역 추가
if (!isVisited[ny][nx] && map[ny][nx].equals("1")) {
// 이동가능하면 탐색영역 추가
queue.add(new Point(ny, nx));
// BFS는 while문에서 돌기때문에 따로 방문체크
// 반면 DFS는 초기에 한번만 방문체크 하면됨(재귀)
isVisited[ny][nx] = true;
}
}
}
}
static class Point {
int y;
int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}// DFS 위 BFS에 설명했으므로 생략
private static void dfs(int y, int x) {
isVisited[y][x] = true;
count++;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
continue;
}
if (!isVisited[ny][nx] && map[ny][nx].equals("1")) {
dfs(ny, nx);
}
}
}정답 출력
// 오름차순 정렬 정답 도출
Collections.sort(answer);
System.out.println(answer.size());
System.out.println(answer.size() == 0 ? 0 : answer.get(answer.size() - 1));
// 내림차순 정렬 정답 도출
// answer.sort(Collections.reverseOrder()); 도 가능
Collections.sort(answer, Collections.reverseOrder());
System.out.println(answer.size());
System.out.println(answer.size() == 0 ? 0 : answer.get(0));🌞 끝으로
DFS, BFS는 정해진 틀이 있으므로 그것을 잘 활용하는게 중요한것 같다. 대부분 저 틀을 활용해서 문제를 풀어왔지만, 조금더 어려운 문제는 3차원 배열을 활용하거나 정답을 다른방식으로 도출하는게 문제일것이다.
🙏