백준 2667번: 단지번호 붙이기 (파이썬, BFS)

BFS로 푸는 문제이다.

아파트가 있는곳은 1, 아파트가 없는곳은 0으로 표시되기 때문에(이진법) 방문여부를 확인하는 배열을 따로 만들지 않고 방문 시 배열값을 0으로 함으로써 다시 방문할 일이 없게 하였다.

근소한 차이긴 하지만 실행시간을 약간이라도 줄이는 것을 확인하였다.

 

import sys
from collections import deque

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


def bfs(x, y):
    global cnt
    graph[x][y] = 0
    q = deque([(x, y)])
    while q:
        now = q.popleft()
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                cnt += 1
                q.append((nx, ny))


N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().strip())))
ans = []

for x in range(N):
    for y in range(N):
        if graph[x][y] == 1:
            cnt = 1
            bfs(x, y)
            ans.append(cnt)
ans.sort()
print(len(ans))
[print(ans[k]) for k in range(len(ans))]