2667

백준 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