[卵殻]冷凍DFS/BFS-<3>飲料

💡 問題の説明

N x Mサイズの氷棚があります.穿孔した部分は0、仕切りがある部分は1と表示されます.穿孔された部分の間が上、下、左、右で接続されている場合は、相互接続とみなされます.所定の氷棚の形状で生成されるアイスクリームの総数を求めるプログラムを作成してください.

💡 入力例

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

💡 出力例

3

💡 ソリューションと回答

DFSは、図面全体にアクセスし、隣接するすべてのセルに1を移動する必要があるため使用します.上、下、左、右で探索を行い、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