[baekjoon] 백준 2667번(파이썬): 단지번호붙이기

문제

- <그림 1>과 같이 정사각형 모양의 지도가 있다.

- 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.

- 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.

- 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.

- 대각선상에 집이 있는 경우는 연결된 것이 아니다.

- <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.

- 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제이다.

- 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력된다.

- 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

알고리즘

- dfs를 통해 연결된 노드를 재귀적으로 모두 확인한다.

- 깊이 탐색을 할때 집의 수를 카운트하여 하나의 단지가 끝나면 집의 수를 리스트에 넣는다.

코드

import sys


# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):

    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 1:
        # 단지의 개수 체크
        cnt.append(1)
        # 해당 노드 방문 처리
        graph[x][y] = 0
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False


# 지도 크기를 입력받는다.
n = int(sys.stdin.readline())
cnt = []
# 2차원 리스트의 맵 정보 입력 받는다.
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 모든 노드(위치)에 대하여 단지 블록을 만든다.
result = 0
result_list = []

for i in range(n):
    for j in range(n):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1
            # 길이를 통해 단지의 개수 확인
            result_list.append(len(cnt))
            cnt = []

# 총 단지의 수 출력
print(result)

# 단지의 수 오름차순 정렬 후 출력
result_list.sort()
for i in result_list:
    print(i)

github

junjange/CodingTest