DFS (2) - 실전문제 5.3) 음료수 얼려 먹기

문제)

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

입력 조건)

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

출력 조건)

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

 

입력 예시)

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시)

8

 

---

이 문제는 DFS 알고리즘으로 해결할 수 있다. N x M의 입력을 받고 2중 for 문을 통해서 리스트의 각 요소에 접근한다. 요소의 값이 0이라는 것은 구멍이 뚫려 있는 부분으로, 만들 수 있는 아이스크림이 1개 추가 되는 것을 의미한다. 따라서 아이스크림을 1개 추가할 때 그 한 덩어리를 모조리 체크해야 한다. 이 부분을 DFS로써 해결할 수 있는 것이다.

먼저, DFS 알고리즘을 수행하기 위해서는 인접 리스트 혹은 인접 행렬이 필요하다는 것을 배웠다. 이 문제에서는 2차원 배열을 입력받기 때문에 각각의 노드는 인덱스 (x값, y값) 값을 갖게 된다. 따라서 인접 행렬을 구현하기에는 복잡하다는 것을 느꼈고 인접 리스트를 구현하기로 했다. 그 방법은 N x M 의 반복문을 돌면서 0인 칸에 대해서 상하좌우에 인접한 0 이 있는 인덱스들을 모두 해당 칸의 값으로 저장하는 것이다.

또한 방문 여부를 체크할 수 있는 N x M 의 2차원 리스트를 생성한다. 그리고 2중 반복문을 돌면서 입력에서 0을 만나게 되면 방문했는지를 체크하고 만약 방문하지 않았다면 DFS 함수를 호출한다. DFS 함수에서는 앞의 예제에서 힌트를 얻어서 해당 인덱스를 방문했다고 체크하고, 생성해둔 인접 리스트의 해당 인덱스에 접근해서 인접한 노드(인덱스) 에 대해 DFS 함수를 재귀적으로 호출하는 것이다. 

이처럼 DFS 함수의 재귀 호출로 인해서 한 덩어리 씩을 체크할 수 있게 된다. 따라서 재귀적인 호출이 아닌 2중 반복문을 돌면서 처음 DFS 함수를 호출하는 횟수를 카운트하게 되면 총 덩어리의 갯수를 셀 수 있는 것이다.

---

책의 답안 예시에서는 인접 리스트를 만들지 않고 DFS 함수 내에서 상하좌우를 모두 호출해서 0인지를 체크 하는 방법을 사용하였다. 이러한 방법을 사용하면 인접 리스트를 만드는 수고를 덜을 수 있기 때문에 소스코드가 조금 더 간단해 질 수 있다는 것을 알게 되었다.