문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
코드
# Using BFS. Push all 1s in queue. make two direction lists dx, dy.
import sys
from collections import deque
n = int(input())
houses = []
for _ in range(n):
houses.append(list(map(int, (input()))))
empty = houses
def bfs(x, y):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = set()
queue = deque()
queue.append((x, y))
while queue:
node = queue.popleft()
x , y = node
if node not in visited: # house
visited.add(node)
empty[x][y] = 0
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < n and 0 <= ny < n and houses[nx][ny] == 1:
queue.append((nx,ny))
return len(visited)
num_list = []
for i in range (n):
for j in range (n):
if empty[i][j]:
num_list.append(bfs(i,j))
lens = len(num_list)
print(lens)
num_list.sort()
for z in num_list:
print(z)풀이
그래프 탐색이 필요한 문제. BFS를 사용했다.
구해야 할 것은
- 총 단지의 수
- 단지 내 아파트의 수
로 두 가지다.
'BFS의 깊이'가 단지 내 아파트의 수를 나타낸다고 생각했었는데 틀렸다... BFS의 깊이는 마지막 노드까지의 거리, 즉 닿는 데까지 걸리는 시간 등을 구할 때 유용하다.
그렇다면 단지 내 아파트의 수는 어떻게 구했을까?
단지 내 아파트의 수는 '방문한 노드의 개수'와 같다. 즉, visited를 사용했다면 visited의 길이를 구하면 된다.
구현 시 주의해야 할 점이 하나 더 있었다. 이전 그래프 탐색 문제들에서는 시작 노드가 정해져 있었고, BFS를 한 번만 하면 됐었지만 이번 문제에서는 BFS를 여러 번 진행하여야 했다.
단지가 여러 개이므로, '시작 노드들'을 찾는 것이 중요했다. 이 부분은 이중 반복문으로 1에 해당하는 노드를 찾으면 되었다. 그러나... 이미 방문한 노드는 재방문해서는 안 됐다. 그러기 위해 이미 방문한 노드들을 1이 아닌 다른 숫자로 바꿔 줄 필요가 있었다. empty 배열을 새로 선언하여 BFS에서 방문한 노드들은 0으로 바꿔주었다.
그래프 탐색 자체는 익숙해졌지만, 나머지 구현에서 어려움을 겪었다.
조금 헷갈렸던 부분은... 이미 방문한 노드를 아예 house에서 0으로 바꾸면 안 되지 않나? 였다. 왜냐하면 이미 방문했는데 다시 되돌아가서 재방문 하고 싶을 수도 있잖아. 였는데... 어차피 내가 노드를 한번 방문한 이상 그 노드에 연결된 다른 노드들은 큐에 존재한다! 그래서 0으로 바꿔줘도 상관없음. 그리고 1에서 0으로 바꿔주는게 visited 표시랑 똑같다.
아직 한참 멀었다. 이거 푸는 데 한 시간은 걸린 것 같은데 ㅎㅎ... 화이팅
