•
풀이
개인적으로 어려워 강의 풀이를 보고 이해했다. 이후 시간이 지난 후, 다시 혼자서 풀어보았다.
아이스크림은 모두 연결하여 하나로 취급하기 때문에, 깊이 탐색을 통해 끝을 확인해야 한다.
문제에서는 그런 덩어리가 전체 몇개냐고 물어봤기 때문에, 한번의 깊이 탐색이 끝나면(하나의 덩어리의 파악이 끝나면) 숫자를 하나 올려주는 방법으로 카운팅했다.
아무래도 강의의 해답을 보고 풀었던 문제라 그런지 다시 풀어도 해설의 코드만 생각난다.
앞으로는 더 혼자서 깊이 고민해보는 습관을 가져야겠다.
def dfs(x, y):
# 탐색이 종료되는 조건
if x < 0 or x >= N or y < 0 or y >= M:
return False
if ICE[x][y] == 0:
ICE[x][y] = 1
dfs(x-1, y)
dfs(x+1, y)
dfs(x, y-1)
dfs(x, y+1)
# 모든 탐색이 끝난 경우
return True
return False
N, M = map(int, input().split())
ICE = []
count = 0
for _ in range(N):
ICE.append(list(map(int, input())))
for i in range(N):
for j in range(M):
# 모든 탐색이 끝난 경우(하나의 덩어리를 모두 찾은 경우)
if dfs(i, j): count += 1
print(count)
Python
복사