NxM 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이 부분은 1로 표시된다. 구멍이 뚫린 부분끼리 상하좌우로 붙어있다면 서로 연결된 것으로 본다. 이때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하여라.
이 문제를 딱 보고 dfs와 bfs 중 어떤 알고리즘을 사용할 지 감이 잘 오지 않았다. 주변에 인접한 0들을 다 찾으면 되니까 둘 다 될 것 같았다.
구글링해보니 처음부터 시작해서 0을 찾게되면 그 0과 이어진 부분을 모두 주우욱 찾아서 덩어리로 보고 한개로 카운트 하기 때문에 bfs가 적합하다고 나와있었다. dfs문제가 처음이라 몰랐는데 한 개에 다 이어진것을 찾아야 한다고 생각하니 맞는 것 같다.
풀이과정
1. 특정 지점의 상하좌우를 살펴본 후 주변 지점에 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상하좌우를 살펴보며 방문하는 것을 반복해나가면 연결된 모든 지점을 방문할 수 있다.
3. 1,2번을 모든 노드에 반복하면서 방문하지 않은 지점의 수를 카운트한다.
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
def dfs(x,y):
if -1 >= x or x >= n or -1>= y or y >= m:
return False
if graph[x][y] == 0: #방문 위치가 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
count = 0
for i in range(n):
for j in range(m):
#재귀적으로 호출이 다 끝나고 true를 반환하면 덩어리 한 개
if dfs(i,j) == True:
count += 1
print(count)
풀이를 다 이해하고 나니 재귀함수라는 것이 엄청나게 간편하게 구현하게 도와주는것을 알게 되어서 신기했다. 이걸 내 손으로 짤 수 있는 날이 빨리 왔으면 좋겠다.
