[Python] 백준 2667 단지번호붙이기

 

문제 분석

• 1 : 집이 있는 곳
• 0 : 집이 없는 곳
• 상하좌우 연결
• 출력 : 단지 수, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력

 

코드 설계

1. 단지의 집 개수를 찾기 위한 시작 집 찾기
   • 1이고, 아직 방문하지 않은 집
2. 집을 찾으면 해당 단지의 가구 수 체크
3. 단지에 해당하는 집을 다 찾으면 단지수 count

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
house = [list(input().strip()) for _ in range(n)]
v = [[False] * n for _ in range(n)]

dan = 0 # 총 단지 수
apts = [] # 아파트의 수를 저장할 배열

d = deque()
dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

# 1. 새로운 단지의 집 찾기 : 처음 시작하는 집은 한번도 방문하지 않은 집
for i in range(n) :
    for j in range(n) :
        if house[i][j] == '1' and not v[i][j] : # 1이면서 아직 방문하지 않은
            v[i][j] = True
            d.append((i,j))

            cnt_apt = 0 # 아파트 수 리셋
            while d:
                # 2. 해당 단지의 아파트 수 세기
                h, w = d.popleft()
                cnt_apt += 1

                for k in range(4) :
                    nh = h + dh[k]
                    nw = w + dw[k]

                    if nh < 0 or nh >= n or nw < 0 or nw >= n :
                        continue
                    if v[nh][nw]: # true : 이미 방문했다면
                        continue
                    if house[nh][nw] != '1' :
                        continue

                    # 해당 단지에 다른 집이 있다면
                    v[nh][nw] = True
                    d.append((nh,nw))

            apts.append(cnt_apt)
            dan += 1

print(dan)
print('\n'.join(map(str, sorted(apts))))