[알감탈] DFS/BFS - <3> 음료수 얼려 먹기

💡 문제 설명

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

💡 입력 예시

4 5		// 4 x 5 맵 생성
00110
00011
11111
00000

💡 출력 예시

3

💡 해결 아이디어 & 풀이

전체 그래프를 방문하며 인접한 칸이 모두 1이 될 때까지 탐색해야 하므로 DFS를 사용한다. 상, 하, 좌, 우를 탐색하며 0이 끝날 때 까지 계속해서 탐색한 후 탐색이 끝났을 경우(인접한 칸이 모두 1인 경우)에 아이스크림의 개수를 1 추가해준다.

package DFS_BFS;
import java.util.Scanner;

public class icecream {
    public static int n, m;
    public static int[][] frame = new int[1000][1000];
    public static int result = 0;

    // dfs 구현 (행, 열이 파라미터로 전달됨)
    public static boolean dfs(int x, int y) {
        if(x<0 || y<0 || x>=n || y>=m) return false;

        // 뚫려있는 경우
        if(frame[x][y] == 0) {
            frame[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) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 빈 줄 처리

        // 틀 입력받기
        for(int i=0; i<n; i++) {
            String line = sc.nextLine();
            for(int j=0; j<m; j++) {
                frame[i][j] = line.charAt(j) - '0';
            }
        }
        
        /**
         * 탐색하면서 0은 방문 체크를 해주고
         * 0인 묶음 내에 있는 경우 묶음 전체를 탐색한 후
         * 모든 탐색이 끝나면 true 반환해주며 result++
         * 이 과정 반복
         */
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                boolean flag = dfs(i,j);
                if(flag) result++;
            }
        }
        System.out.println(result);
        sc.close();
    }
}

*참고: https://github.com/ndb796/python-for-coding-test