[백준] 음료수 얼려 먹기

📖 문제

N x M 크기의 얼음 틀이 있고 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다.

구멍이 꿇려있는 부분끼리 상, 하, 좌, 우 붙어 있는 경우 서로 연결되어 있다는 것으로 간주합니다.

얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요.

✍ 입력

첫째 줄에 얼음 틀의 세로 길이 N 과 가로 길이 M dl 주어집니다 (1 <= N, M <= 1000)

두번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어집니다.

이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1입니다.

📄 출력

한번에 만들 수 있는 아이스크림의 개수를 출력합니다.

✅ 코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
    private static int N = 0;
    private static int M = 0;
    private static int[][] graph = new int[1000][1000];

    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 str = sc.nextLine();
            for(int j=0; j<M; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

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

        System.out.println(result);
    }

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

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

            bfs(x-1, y);
            bfs(x, y-1);
            bfs(x+1, y);
            bfs(x, y+1);
            return true;
        }
        return false;
    }

🧩 코드풀이

1. 배열에서 값이 0이면 주변을 탐색하여 1로 바꿔준다.
2. 방문 후 true를 반환하고 방문하지 않으면 false를 리턴해준다.
3. 반환 값이 true일 때 result 값을 +1 하여 출력해준다.