문제
문제 : https://www.acmicpc.net/problem/2667
그림 1과 같이 정사각형 모양의 지도에서 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 이 지도에서 상하좌우 방향으로 인접한 집의 모임을 단지로 정의하고, 단지에 번호를 붙이려고 한다.
그림 2는 그림 1을 단지별로 번호를 붙인 뒤 색을 달리하여 표시한 것이다.
지도를 입력받아 단지의 수와 단지 별 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하라.
접근
그래프 탐색 방법인 DFS나 BFS를 사용하여 풀어낼 수 있다. 최단 경로를 요구하지 않으므로 DFS, BFS 중 편한 방법으로 구현하면 될 것 같다.
다만 지도 내 단지가 하나 이상이므로 테이블 전체를 순회하면서 그래프 탐색을 수행해야 한다. 아무 조건 없이 테이블을 순회하면서 그래프 탐색을 수행하면 불필요한 반복이 발생할 수 있기 때문에 효율성에서 이득을 얻고 싶다면 그래프 탐색 시작점의 방문 여부 확인하여 탐색 수행 여부를 결정해야 하겠다.
구현
이 글의 경우에는 BFS를 사용하여 구현했다.
1. 입력값 초기화
지도의 크기 n과 지도를 입력 받는다.
n = int(sys.stdin.readline())
maps = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]
2. BFS 시작점의 방문 여부를 저장할 visited와 단지 별 집의 수를 저장할 list_cnt를 선언한다.
visited = [[False for _ in range(n)] for _ in range(n)]
list_cnt = []
3. BFS 수행
지도를 순회하면서 BFS를 수행한다.
def bfs(maps, n, m, start=(0, 0)):
visited = [[False for _ in range(m)] for _ in range(n)]
directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]
queue = [start]
visited[start[0]][start[1]] = True
while queue:
i, j = queue.pop(0)
for x, y in directions:
ni, ny = i + x, j + y
if 0 <= ni < n and 0 <= ny < m and maps[ni][ny] == 1:
if visited[ni][ny] == 0:
queue.append((ni, ny))
visited[ni][ny] = True
return visited
for i in range(n):
for j in range(n):
if maps[i][j] == 1 and not visited[i][j]:
temp = bfs(maps, n, n, start=(i, j))
visited = [[temp[x][y] | visited[x][y] for y in range(n)] for x in range(n)]
list_cnt.append(len([i for i in sum(temp, []) if i]))BFS는 별도 함수로 분리하였으며, 시작점을 지정할 수 있도록 구현해야 한다.
bfs를 수행하면 지도 내 집 방문 여부를 저장한 결과를 얻을 수 있는데, 해당 결과는 visited에 OR 조건으로 업데이트해야 한다.
그리고 bfs 수행 결과 중 값이 True인 개수를 list_cnt에 추가한다.
참고로 bfs는 지도의 집이 있는 경우(값이 1인 경우), 그리고 아직 방문하지 않은 경우에 수행해야 중복 탐색을 방지할 수 있다.
4. 결과 출력
list_cnt의 개수, 그리고 list_cnt 내 값을 정렬하여 출력한다.
list_cnt.sort()
print(len(list_cnt))
print("\n".join(str(n) for n in list_cnt))
참고 문서
https://www.acmicpc.net/problem/2667