[이코테] 20강 '음료수 얼려 먹기'

문제

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

 

문제 조건

풀이 시간 30분, 시간제한 1초, 메모리 제한 128MB

 

입력

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

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

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

 

출력

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

---

'문제 해결 아이디어'

특정 노드에서 DFS, BFS를 수행해 이동 가능한 모든 경로에 대해 다 방문 처리를 진행하도록 함.

'1'인 노드는 이동이 불가능한 노드로 판단되게 해 이동이 불가능하게 함.

방문처리가 이루어지는 지점에 대해서만 카운팅 해주면 전체 얼음의 개수를 파악할 수 있음.

 

'정답 코드'

- DFS 사용

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

n, m = map(int, input().split())

graph = []

for i in range(n):
    graph.append(list(map(int, input())))

# dfs로 특정 노드를 방문하면서 그와 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나면 즉시 종료
    if x <= -1 or x >= n or y <= -1 or 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
  
# 모든 노드(위치)에 대해 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result)

 

⭐ point!

- 상, 하, 좌, 우의 위치들을 탐색할 땐 return값을 사용하지 않기 때문에 단순히 연결된 모든 노드에 대해 방문 처리를 수행하기 위한 목적

- 즉, 위에서 설계된 dfs 함수는 한 번 수행되면 해당 노드와 연결된 모든 노드들도 방문 처리할 수 있도록 하고, 그 시작점 노드가 방문 처리가 되었다면 그때만 result 값을 증가시킴