[이것이 코딩 테스트다 with Python] 음료수 얼려 먹기(Java)

Goal

“이것이 코딩 테스트다 with Python” 교재의 문제를 분석하고 코드와 함께 이해해보기 위한 글입니다.

문제 분석

얼음 틀을 배열로 구현한 후 DFS를 해서 요구하는 결과값을 구하는 프로그램을 작성해겠습니다.

코드 구현

public class FrozenDrinkEat { //p151

    static int[][] frame;
    static int row;
    static int col;

    public static boolean dfs(int i, int j) {
        if (i < 0 || i >= row || j < 0 || j >= col) return false; //얼음 틀 벗어나는 범위
        if (frame[i][j] == 0) {
            frame[i][j] = 1; //해당 노드 방문처리
            //인접한 부분도 얼릴 수 있는 칸인지 확인(재귀 함수)
            dfs(i + 1, j);
            dfs(i, j + 1);
            dfs(i - 1, j);
            dfs(i, j - 1);

            return true;
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken()); //얼음 틀의 행 갯수
        col = Integer.parseInt(st.nextToken()); //얼음 틀의 열 갯수
        frame = new int[row][col];
        int answer = 0;

        for (int i = 0; i < row; i++) {
            String[] strArr = br.readLine().split("");
            for (int j = 0; j < col; j++) {
                frame[i][j] = Integer.parseInt(strArr[j]); //틀 모양 적용
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(i, j)) {
                    answer++;
                }
            }
        }
        System.out.println(answer);
        br.close();
    }
}