[이코테] DFS/BFS - 음료수 얼려 먹기

문제

아이디어

dfs 함수는 구멍이 뚫려있는 부분(0인 부분)을 발견하였을 때 True를 return 하는 함수이다.

1️⃣반복문에서 현재 확인하는 노드 값이 범위를 벗어나면 False를 return 한다.
2️⃣반복문에서 현재 확인하는 노드 값이 0(구멍)이라면 두번째 if문으로 들어간다.
현재 노드에 대해 방문처리를 진행한 후, 현재 노드를 기준으로 최대한 깊게 탐색하여 연결된 뚫려있는 부분(0)을 1로 만든 후 True를 return 한다. (재귀호출이 차례로 종료되고 return True)
3️⃣반복문에서 현재 확인하는 노드 값이 0이 아닌 칸막이라면 False를 return 한다.


dfs 함수의 return 값이 True인 경우에만 result를 증가시켜 아이스크림의 개수를 구한다.

풀이

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 # 방문처리 (그래프 값 자체를 1로 변경)
        # 상하좌우 노드에 대해 재귀호출 - 상하좌우 노드 값이 0인 경우 방문하며 1로 변경
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True # 0(구멍)이므로 true
    return False # 1(칸막이)이므로 false

# 모든 노드에 대해 확인
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1

print(result)

Comment

return True False 부분이 이해가 잘 되지 않아 여러 글을 참조하고 손으로 직접 과정을 따라가보니 이해가 되었다.
그래프 값 자체를 1로 바꾸어줌으로써 방문처리 하는 것도 새로웠다.