[백준] #2667 단지번호붙이기 (python)

https://www.acmicpc.net/problem/2667

문제풀이

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

N=int(input())
#단지 지도 받기
matrix=[]
for _ in range(0,N):
    matrix.append(list(map(int,input().strip())))
#방문 여부 판단하기 위해서 크기가 같은 지도 만들기
visited= [[False for _ in range(0,N)] for _ in range(0,N)]
#단지내 집의 수를 넣기 위한 리스트 만들기
town=[]

def bfs(x,y,matrix):
    house_cnt=1
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    visited[x][y]=True
    queue=deque()
    queue.append((x,y))

    while queue:
        cur_x,cur_y=queue.popleft()
        for k in range(0,4):
            next_x=cur_x+dx[k]
            next_y=cur_y+dy[k]
            if 0<=next_x<N and 0<=next_y<N:
                if matrix[next_x][next_y]==1 and not visited[next_x][next_y]:
                    queue.append((next_x,next_y))
                    visited[next_x][next_y]=True
                    house_cnt+=1

    town.append(house_cnt)

for i in range(0,N):
    for j in range(0,N):
        if matrix[i][j]==1 and  not visited[i][j]:
            bfs(i,j,matrix)
            
print(len(town))
town.sort()
for i in town:
    print(i)

#단지내 집의 수를 세는 변수
#단지내 집의 수를 저장하기 위한 리스트
#1이면서 방문하지 않은 false인 경우 bfs 수행
#한번 그 묶음을 돌면 전부다 true 처리
#반복문 수행
#리스트 길이로 단지수 출력하고
#리스트 정렬하고 출력

정리

이중 반복문을 이용하여 지도의 모든 좌표마다 1이면서 방문하지 않은 곳이라면 bfs를 수행한다.

bfs에서 상하좌우로 움직이면서 1이면서 방문하지 않은 경우 계속 너비 우선 탐색을 실행하고 인접한 집을 다 방문할 때까지 반복문을 통해서 수행한다.

한 단지내의 집의 수를 알기위해 집을 방문할 때마다 1씩 증가시켜 관리해주고 한 단지를 다 방문하면 집의 수를 town 리스트에 넣어준다.

town 길이를 출력해서 단지 수를 출력하고 리스트를 정렬한 후에 오름차순으로 출력한다.