BOJ 2667번 : 단지번호붙이기 (Python/Silver 1)

2667번: 단지번호붙이기

---

설명

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 1로 연결된 곳은 하나의 단지다. (대각선에 집이 있는 경우는 연결된 것이 아니다.) <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 총 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

풀이

✓ BFS 알고리즘 이용

https://dev-cloud.tistory.com/161 -> 유사한 문제이다. BFS와 관련해서 더 자세한 설명이 있으니 봐보자.

Solution 

import sys
input = sys.stdin.readline #입출력 향상
from collections import deque #덱 라이브러리(큐를 사용하기 위함)

# 좌우상하
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(i, j):
    visited[i][j] = 1 #방문 표시
    q = deque() #큐 생성
    q.append((i, j)) #큐에 초기 위치 넣기
    homecnt = 1 #집의 수

    while q:
        x, y = q.popleft() #큐에서 현재 위치 빼내기

        for z in range(4): #현재 위치에서 좌우상하 확인
            nx = dx[z] + x 
            ny = dy[z] + y

            if -1 < nx < N and -1 < ny < N: #지도 범위를 벗어나지 않아야 하는 조건
                if visited[nx][ny] == 0 and graph[nx][ny] == 1: #집이 있는데 방문하지 않았으면
                    visited[nx][ny] = 1 #방문 표시
                    homecnt += 1 #집의 수 카운트
                    q.append((nx, ny)) #큐에 이동한 위치 넣기
    homeans.append(homecnt) #탐색 끝났으면 집의 수 리스트에 넣기(정렬을 위해서 리스트에 저장)

N = int(input())
graph = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[0]*N for _ in range(N)] #0은 방문하지 않은 상태
cnt = 0 #단지 수
homeans = [] 

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0 and graph[i][j] == 1: #집이 있는데 방문하지 않았으면
            cnt += 1 #단지 수 카운트
            bfs(i, j)

print(cnt) #단지 수 출력
homeans.sort() #오름차순 정렬이므로 리스트에 저장된 집의 수 정렬해주기
for i in homeans: #정렬된 집의 개수 출력
    print(i)