이 문제는 0인 값이 상하좌우로 연결되어 있는 노드를 묶는 것이다.
그러기 위해서는 특정 지점에서의 상하좌우의 값이 0인지를 확인하고 0이면서 동시에 방문하지 않았다면, 그곳을 방문해야한다.
그리고 그 방문한 지점에서 상하좌우의 값이 0인지를 확인하고 0인 지점이 있다면 방문여부를 확인한다.
이 과정을 반복하여, 상하좌우의 값이 1이거나 방문한 곳일 경우에 반복을 멈추고 카운트를 하나 올린다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
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, y-1)
dfs(x+1, y)
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)
dfs 함수를 보면, 상하좌우를 확인하기 위해 재귀를 4번 실행하고 있는데 이는 꽤나 인상깊다.
맨 처음 내가 문제를 접하고 풀이를 고민해봤 때, 별도의 반복문을 통해 상하좌우를 체크해야하지 않나 싶었기 때문이다.