DFS - 음료수 얼려 먹기

< 음료수 얼려 먹기 > 

[문제]

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

[입력]

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

[출력]

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

예제 입력	예제 출력
4 5 00110 00011 11111 00000	3

---

아이디어

이 문제에서는 방문처리를 tray에 바로 해준다. 즉 방문 한 것도 1, 칸막이도 1로 같다. (더이상 접근하지 말아야 하는 것은 똑같으므로) 이중 포문을 돌면서 모든 점에 하나하나 접근한다. 만약 접근한 칸이 0이라면 dfs함수를 호출해준다. dfs함수는 사방으로 인접한 주변 칸에 접근하여 0이면 1로 바꿔주고 또 다시 dfs함수를 재귀적으로 호출한다. 그렇게 되면 tray의 0을 만나게 되면 dfs 함수를 한 번 부르고 그 함수가 재귀적으로 dfs함수를 호출하여 결국 이어져 있는 0들이 모두 1이 된다. 포문에서 한 번 dfs함수를 호출할 때 카운트를 증가시켜준다.

풀이 및 코드

tray = []
n, m = map(int, input().split())
for _ in range(n):
    tray.append(list(map(int,input())))
# 네 방향
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(row, col):
    # 0인 점을 1로 바꿔줌.
    tray[row][col] = 1
    for direction in move:
        new_row = row + direction[0]
        new_col = col + direction[1]
        # 범위 벗어나면 다음 방향 보기
        if (not 0 <= new_row < n) or (not 0 <= new_col < m):
            continue
        # 이미 접근 했으면 다음 방향 보기
        if tray[new_row][new_col]:
            continue
        dfs(new_row, new_col)
        
cnt = 0
for row in range(n):
    for col in range(m):
        # tray[row][col]이 0이면 카운트 증가 및 dfs호출
        if not tray[row][col]:
            cnt += 1
            # dfs함수에 들어가게 되면 현재 위치와 연결된 모든 0을 1로 바꿔줌.
            # 따라서 같은 0을 다시 세는 일은 없음.
            dfs(row, col)
print(cnt)

후기

나동빈님 강의 코드

강의를 들었는데 나동빈님이 짠 코드가 훨씬 더 간결해보인다. 재귀함수의 리턴 값을 활용하는 것도 좋은 것 같다.