[백준/2667/파이썬] 단지번호붙이기

소스코드

from collections import deque

N = int(input())

graph = []

for i in range(N):

    graph.append(list(map(int, input())))

def bfs(graph,x,y):

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

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

  queue = deque()

  queue.append((x,y))

  graph[x][y] = 0

  cnt = 1

  while (queue) :

    x,y = queue.popleft()

    for i in range (4):

      ax = x + dx[i]

      ay = y + dy[i]

      if (ax < 0) or (ax >= N) or (ay < 0) or (ay >=N):

        continue

      if graph[ax][ay] == 1:

        graph[ax][ay] = 0

        queue.append((ax,ay))

        cnt += 1  

  return cnt

  

count = [bfs(graph, i, j) for i in range(N) for j in range(N) if graph[i][j] == 1]

count.sort()

print(len(count))

for i in range(len(count)):

    print(count[i])

 

알고리즘

BFS 문제입니다. 이전 문제들과 마찬가지로 queue를 선언해서 상하좌우를 queue에 넣어가며 진행하면 되는데요

아파트 단지를 탐색하면서 진행을 하는데 단지가 하나가 아니라 여러개가 있어서 다른문제와는 다르게 이미 지나온 곳을 0으로 바꾸어 줬습니다. 그리고 출력은 graph가 1인 부분에서 bfs를 실행하였고 결과적으로 count라는 리스트에 단지 내의 아파트 개수가 저장이 됩니다.