백준 2667 python

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

from collections import deque

n = int(input())
cnt = 0
mapCnts = []
arr = []
moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]

def bfs(a, b):
    Q = deque()
    Q.append((a, b))
    arr[b][a] = 0
    mapCnt = 1
    
    while Q:
        x, y = Q.popleft()
        
        for i in range(4):
            ny = y + moveY[i]
            nx = x + moveX[i]
        
            if(ny < 0 or nx < 0 or ny >= n or nx >= n):
                continue
            
            if(arr[ny][nx] == 1):
                Q.append((nx, ny))
                arr[ny][nx] = 0
                mapCnt += 1

    mapCnts.append(mapCnt)

    
for i in range(n):
    arr.append(list(map(int, input())))

for y in range(n):
    for x in range(n):
        if(int(arr[y][x]) == 1):
            bfs(x, y)
            cnt += 1
            

mapCnts.sort()
print(cnt)
for i in range(cnt):
    print(mapCnts[i])

풀이

이번 문제도 인접 행렬 bfs 문제였다.

이중 반복분을 통해서 모든 노드에 방문하면서 1인지 확인하고

bfs 함수 호출 시 근접해있는 노드들을 모두 0으로 변경!

단지의 개수들은 그냥 bfs 함수에서 큐에 더이상 값이 없을 때

즉 while문이 종료되면 특정 배열에 넣어주면 된다.

좋았어