문제
https://www.acmicpc.net/problem/2667
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class Main {
public static int[] dx = {1, 0, -1, 0};
public static int[] dy = {0, 1, 0, -1};
public static int N;
public static int count = 0;
public static int[][] matrix;
public static boolean[][] visit;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine());
matrix = new int[N + 1][N + 1];
visit = new boolean[N + 1][N + 1];
List<Integer> result = new ArrayList<>();
for (int i = 0; i < N; i++) {
String[] line = bf.readLine().split("");
for (int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(line[j]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j] && matrix[i][j] == 1) {
dfs(i, j);
result.add(count);
count = 0;
}
}
}
System.out.println(result.size());
result = result.stream()
.sorted()
.collect(Collectors.toList());
result.forEach(System.out::println);
}
public static void dfs(int x, int y) {
visit[x][y] = true;
count++;
int nextX, nextY;
for (int i = 0; i < 4; i++) {
nextX = x + dx[i];
nextY = y + dy[i];
if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
if (!visit[nextX][nextY] && matrix[nextX][nextY] == 1) {
dfs(nextX, nextY);
}
}
}
}
}
풀이 방법
- 2차원 배열에 0과 1로 이루어진 지도를 저장한다. 이 배열에서 1로 이루어진 부분이 바로 그래프가 된다.
- visit 배열도 2차원 배열로 준비한다.
- 이중 for문을 통해 방문하지 않은 정점이면서 값이 1인 정점에 대해서
dfs를 호출한다.💡왜??- 2차원 배열 내부에서 그래프의 존재를 판단 해야되기 때문이다.
- 값이 1이면서 아직 방문하지 않은 노드는 새로운 그래프의 시작점을 나타낸다.
- 문제의 Test케이스를 실행했을 떄 if문 내부에서 인덱스를 출력하면 다음과 같이 시작점이 나타난다.
- dfs 내부에서는 호출 후, visit 배열을 true로 바꾸고 count를 1증가 시킨다.
nextX,nextY값은 정점의 다음 좌표를 나타낸다.dx,dy값은 정점을 기준으로 위, 아래, 왼쪽, 오른쪽을 나타내게 된다.
for (int i = 0; i < 4; i++)를 통해 해당 정점의 다음 좌표가 범위 안에 있는지 판단한다.
- 만약 범위안에 있다면, 다시 visit 배열과 matrix를 판단하여 재귀호출한다.
핵심 포인트
- dfs에서만 조건을 확인하는 것이 아닌, 외부에서도 조건을 확인하여 호출해야 한다. 그렇게 함으로써 아직 조회되지 않는 노드들의 인접 노드의 개수를 파악할 수 있다.
- dfs 내부에서 상, 하, 좌, 우를 판단하여 값이 유효한지 판단하고, 조건 검사를 진행해야 한다.
보완할 점 / 느낀 점
- 이런 류의 문제를 처음 풀어봐서 굉장히 어려웠다. 처음 1시간 정도 문제를 붙잡고 있다가, 도저히 갈피를 못찾아서 문제를 찾아봤다.
- 간과하고 있던 아이디어는 단순히
DFS만 사용하는 것이 아닌, 메서드 내부에서 상, 하, 좌, 우가 유효한지 판단한 후 재귀호출을 해야한다는 것이었다. 이 아이디어를 생각하지 못하면, 절대 해결하지 못할 문제였다.
- 갓 기본적인 DFS 알고리즘이랑 뼈대 문제 몇개 푼 후 접근하기엔 난이도가 있었다.
- 이런 류의 문제를 더욱 많이 풀어봐야겠다.
참고자료