백준 2667: 단지번호붙이기 해설- python

✏️ 문제

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

2667번: 단지번호붙이기

 

✏️ 풀이

BFS가 편해서 BFS를 이용해서 풀이하였다.

백준 2178: 미로찾기와 백준 11724: 연결요소의 개수 가 혼재된 느낌의 문제였다. 두개 문제의 아이디어를 섞으면 풀린다.

그래프 탐색 시작점을 모르니까 그래프 전체를 반복문으로 돌면서 bfs를 시작한다. 이때 bfs를 하면서 탐색이 된 위치는 0으로 바꾸어 다시 탐색하는 일이 없도록 해주면 된다. 이렇게해서 bfs()를 몇번 실행하는지를 출력하면 단지의 개수가 출력된다. 

 

from collections import deque

dx=[-1,1,0,0]
dy=[0,0,1,-1]
#입력
n=int(input())
matrix=[]
for _ in range(n):
  matrix.append(list(map(int,input())))

#bfs 구현
def bfs(a,b):
    queue=deque([[a,b]])
    matrix[a][b]=0 # 탐색 마친곳을 0으로해서 다시탐색안하도록
    count=0 # 단지내 집수를 카운트할거다.
    while queue:
      x,y=queue.popleft()
      count+=1
      for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and matrix[xx][yy]==1:
          matrix[xx][yy]=0
          queue.append([xx,yy])
    return count

stack_output=[]
for i in range(n):
  for j in range(n):
    if matrix[i][j]==1:
      stack_output.append(bfs(i,j))

print(len(stack_output))
stack_output.sort()
for out in stack_output:
  print(out)