백준 2667번 단지번호붙이기 (Python, BFS)

문제 이해

2차원 그래프 (NxN)이 주어진다.
1은 집이 있다는 것을 의미하고 0은 집이 없음을 의미한다.
각 집들이 상하좌우로 이어져있다면 이를 하나의 단지로 본다.
대각선은 하나의 단지가 아니다.
우리는 이 단지가 몇개가 있는지, 각 단지의 집의 개수는 몇개인지를 알아내야한다.

아래의 그림을 보면 3개의 단지가 있음을 알 수 있다.

문제 접근

지도가 주어지고 완전탐색해야하는 문제이기 때문에 BFS를 생각했다. 물론 DFS로도 풀 수 있다.
따라서 2가지로 나누었는데,

• 이어져있는 집들 확인 (BFS)
• 이어져있는 집들의 개수 count 리스트에 넣고 sort하여 내림차순으로 정렬

문제 풀이

이어져있는 집들 확인(BFS)

현재 a,b 좌표에 위치해 있다.
현재의 좌표의 house를 0으로 만들고 이어져있는 집들의 개수를 확인하는 friend라는 변수를 1로 초기화한다. (현재 좌표 집 1개)
이제 for문을 통해 상하좌우를 확인하면서 house가 1이라면 큐에 넣어주고 house를 0으로 만들어준다. 또한 집들의 개수확인을 위해 friend에 1을 더해준다.
마지막으로 모든 연결된 집들을 0으로 만들고 개수를 확인했다면 count리스트에 friend를 추가해준다.

main함수에서 house가 1이라면 bfs(i,j)를 실행하기 때문에 만약 이미 단지의 개수에 추가된 집이라면 house가 0이 되므로 중복으로 실행되지 않는다. 따라서 bfs는 단지의 개수만큼만 실행될 수 있다.

dx = [0,0,-1,1]
dy = [1,-1,0,0]
count = []
def bfs(a, b):
    q = deque()
    friend = 1
    q.append((a,b))
    house[a][b] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i] 
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            if house[nx][ny]==1:
                q.append((nx,ny))
                house[nx][ny] = 0
                friend += 1
    count.append(friend)
    
    
for i in range(N):
    for j in range(N):
        if house[i][j] == 1:
            bfs(i, j)

이어져있는 집들의 개수 count 리스트에 넣고 sort하여 내림차순으로 정렬

count에는 각 단지의 개수가 들어있을 것이다.
따라서 count리스트의 전체 길이를 출력하면 몇개의 단지가 있는지 출력된다.
내림차순으로 정렬하고 count를 pop해주면서 출력하면 오름차순으로 출력이 된다.

print(len(count))
count.sort(reverse=True)
while count:
    print(count.pop())

제출 코드

import sys
from collections import deque
N = int(sys.stdin.readline())
house = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
# 이어져있는 집들 확인 (BFS)
# 이어져있는 집들의 개수 count 리스트에 넣고 sort하여 내림차순으로 정리

dx = [0,0,-1,1]
dy = [1,-1,0,0]
count = []  
def bfs(a, b):
    q = deque()
    friend = 1
    q.append((a,b))
    house[a][b] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i] 
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            if house[nx][ny]==1:
                q.append((nx,ny))
                house[nx][ny] = 0
                friend += 1
    count.append(friend)

for i in range(N):
    for j in range(N):
        if house[i][j] == 1:
            bfs(i, j)

print(len(count))
count.sort(reverse=True)
while count:
    print(count.pop())