[파이썬] 백준 2667번 문제: 단지번호붙이기

단지 번호 붙이기

📄 문제

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다.
1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고,단지에 번호를 붙이려 한다.
여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.
지도를 입력하여 단지수를 출력하고,
각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고,
그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오.
그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

🧞 풀이

풀이

# [파이썬] 백준 2667번 문제: 단지번호붙이기

from collections import deque                                                                           # deque 불러오기

n = int(input())                                                                                        # n 입력 및 할당
apt = [list(map(int, input())) for _ in range(n)]                                                       # apt 배열 입력 및 할당

dx = [1, -1, 0, 0]                                                                                      # 좌, 우 이동 dx 할당
dy = [0, 0, 1, -1]                                                                                      # 상, 하 이동 dy 할당

Q = deque()                                                                                             # BFS를 위한 빈 Q 할당
check = [[0] * n for _ in range(n)]                                                                     # 방문 확인을 위한 check n * n 크기의 배열로 할당

a_list = []                                                                                             # 정답을 담을 빈 a_list 할당

for i in range(n):                                                                                      # n만큼 이중반복
    for j in range(n):
        if apt[i][j] == 1 and check[i][j] != -1:                                                        # 집(1)이면서, 방문하지 않았을 때(not -1)
            check[i][j] = -1                                                                            # 방문한 것으로 표시 (-1)
            cnt = 1                                                                                     # 단지의 아파트 갯수 1로 할당
            Q.append((i, j))                                                                            # Q에 x 좌표 i와 y 좌표 j 추가

            while Q:                                                                                    # Q에 요소가 들어 있다면
                x, y = Q.popleft()                                                                      # Q에서 popleft하여 x, y에 값 할당
                for l in range(4):                                                                      # 상하좌우로 반복
                    nx = dx[l] + x
                    ny = dy[l] + y
                    if 0 <= nx < n and 0 <= ny < n and check[nx][ny] != -1 and apt[nx][ny] != 0:        # nx와 ny가 아파트 배열 범위 내에 있으며, 방문하지 않았고 (not -1), 집이 아니지 않을 때 (not 0):
                        check[nx][ny] = -1                                                              # 방문한 것으로 표시 (-1)
                        cnt += 1                                                                        # 집 갯수 1 추가
                        Q.append((nx, ny))                                                              # Q에 nx, ny 추가

            else:                                                                                       # Q에 요소가 없다면
                a_list.append(cnt)                                                                      # 아파트 단지 당 집 최종 갯수를 a_list에 추가

print(len(a_list))                                                                                      # a_list의 길이 출력
a_list.sort()                                                                                           # a_list 오름차순 정렬
for a in a_list:                                                                                        # a_list의 요소 하나씩 꺼내서
    print(a)                                                                                            # 출력