Baekjoon 2667번 단지번호붙이기

문제

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

걸린 시간

00 : 23 : 42

풀이

Python3

from collections import deque

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(loc):
    q = deque()
    q.append(loc)
    town[loc[0]][loc[1]] = 0
    count = 1

    while q:
        x, y = q.popleft()

        for i in range(0, 4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if town[nx][ny] == 1:
                    count += 1
                    town[nx][ny] = 0
                    q.append([nx, ny])

    return count 

def connected():
    count = []
    for loc in house:
        x, y = loc
        if town[x][y] == 1:
            count.append(bfs(loc))

    return count

if __name__ == "__main__":
    N = int(input())

    town = []
    house = []
    for i in range(0, N):
        row = list(map(int, input()))
        for j in range(0, N):
            if row[j] == 1:
                house.append([i, j])    
        town.append(row)    

    result = connected()
    result.sort()
    print(len(result))    
    for i in result:
        print(i)

연결요소의 개수를 구하는 DFS, BFS 문제.