[DFS/BFS] 음료수 얼려 먹기

문제

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

 

예시

00110
00011
11111
00000

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

 

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N,M <= 1,000)
• 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 아닌 부분은 1이다.

출력 조건

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

---

아이디어

이 문제는 DFS로 해결할 수 있다.

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

N, M 입력받고 그래프 초기화

// N x M 입력 받기
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

// 인접 행렬 입력
graph = new int[N][M];
for (int i = 0; i < N; i++) {
    String line = br.readLine();
    for (int j = 0; j < M; j++) {
        graph[i][j] = line.charAt(j) - '0';
    }
}

 

그래프에서 0인 부분에 대해 탐색을 진행한다. 0인 경우 DFS를 호출하고, 1로 바꿈으로써 방문 처리

private static boolean DFS(int x, int y) {
    // 범위를 벗어나면 즉시 종료
    if (x < 0 || y < 0 || x >= N || y >= M) return false;

    // 현재 노드를 아직 방문하지 않았다면
    if (graph[x][y] == 0) {
        // 해당 노드 방문 처리
        graph[x][y] = 1;
        // 상,하,좌,우 위치 모두 재귀 호출
        DFS(x - 1, y);
        DFS(x + 1, y);
        DFS(x, y - 1);
        DFS(x, y + 1);
        return true;
    }
    return false;
}

 

위 함수를 모든 노드에 대하여 실행시킨 후 결과를 출력한다.

int result = 0;
for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
        if (DFS(i,j))
            result++;
    }
}
System.out.println(result);

 

결론

아직 DFS, BFS에 대해 익숙하지 않다. 탐색 문제를 모두 그래프 형태로 표현한 다음 BFS or DFS를 적용시켜 문제를 푸는 연습이 필요할 것 같다.