N X M 크기의 얼음 틀이 있다.
구멍이 뚫려 있는 부분은 0
, 칸막이가 존재하는 부분은 1
로 표시된다.
구멍이 뚫혀 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생서오디는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
입력조건
첫 번째 줄에 얼음 틀의 세로 길이 N
과 가로 길이 M
이 주어진다. (1 ≤ N, M ≤ 1000)
두 번째 줄부터 N + 1
번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0
, 그렇지 않은 부분은 1
이다.
출력조건
import time
n,m = map(int, input().split())
#2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
start = time.time()
#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
#상, 하, 좌, 우의 위치 모두 재귀적으로 호출
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)
print(time.time()-start)
이 문제는 DFS로 해결할 수 있다.
얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링할 수 있다.
예를 들어, 3 X 3 크기의 얼음 틀이 있다고 가정하면, 이는 다음과 같은 그래프로 모델링 할 수 있다.
0
인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶으면 다음과 같이 세 묶음이 나올 것이다.
이러한 묶음을 DFS로 찾는 방법은 다음과 같다.
특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 0
이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
1 ~ 2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.