이것이 취업을 위한 코딩 테스트다. BFS/DFS [음료수 얼려 먹기]

이것이 취업을 위한 코딩 테스트다. with 파이썬 - 나동빈

문재 해설 & 느낀점

public class FreezeDrinks {
    static int N, M;
    static int[][] matrix = new int[1000][1000];

    static boolean dfs(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= M) {
            return false;
        }

        if(matrix[x][y] == 0) {
            matrix[x][y] = 1;

            dfs(x + 1, y);
            dfs(x - 1, y);
            dfs(x, y + 1);
            dfs(x, y - 1);

            return true;
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);

        for(int i = 0; i < N; i++) {
            String[] split = br.readLine().split("");
            for(int j = 0; j < M; j++) {
                matrix[i][j] = Integer.parseInt(split[j]);
            }
        }

        int answer = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(dfs(i, j)) {
                    answer++;
                }
            }
        }

        System.out.println(answer);
    }
}

DFS, BFS 부분을 한번 더 읽어 보았지만 이론으로는 알겠는데 코드로 어떻게 접근해야 할 지 어려움이 느껴져서 해설을 참조했다.

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 열결된 모든 지점을 방문할 수 있다.
3. 1, 2 의 과정을 반복하며 방문하지 않은 지점의 수를 센다.