[baekjoon] 백준 2667번 : 단지번호붙이기 (by python 파이썬) bfs

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

2667번: 단지번호붙이기

 

정답 code

-bfs이용

#단지번호붙이기
#bfs
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(a,b):
    n = len(apt)
    queue  = deque()
    queue.append((a,b))
    apt[a][b] = 0
    count = 1

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue
            if apt[nx][ny] == 1:
                queue.append((nx,ny))
                apt[nx][ny] = 0
                count += 1

    return count

n = int(input())
apt = []
for i in range(n):
    apt.append(list(map(int,input())))

cnt = []
for i in range(n):
    for j in range(n):
        if apt[i][j] == 1:
            cnt.append(bfs(i,j))

cnt.sort()
print(len(cnt))

for i in range(len(cnt)):
    print(cnt[i])

 

solution

이 문제는 다른 너비 우선탐색이나 깊이우선 탐색을 이용해 풀면되는데,

출력조건인 총 단지수와 단지내 집의 수를 오름차순 출력해야 한다.

 

이를 위해 cnt 리스트를 만들고 단지내 집의수를 넣은뒤

리스트의 길이를 단지수, 리스트 인덱스 하나하나를 출력해 집의 수를 출력하면 된다.