[백준 2667번 / 실버1] 단지번호붙이기 - (Graph Traversal)

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

2667번: 단지번호붙이기

 

from collections import deque

def apart(data):
  num,cnt=0,0
  result=[]
  queue=deque()
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  for i in range(n):
    for j in range(n):
      if data[i][j]==1:
        queue.append([i,j])
        data[i][j]=0
        cnt+=1
        while queue:
          x,y=queue.pop()
          for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<n and 0<=ny<n:
              if data[nx][ny]==1:
                queue.append([nx,ny])
                data[nx][ny]=0
                cnt+=1
        result.append(cnt)
        cnt=0
        num+=1
  print(num,*(sorted(result)),sep='\n')

n=int(input())
data=[list(map(int,input())) for _ in range(n)]
apart(data)

사실상 이 문제와 거의 똑같다고 봐도 무방한 문제이다.

BFS를 통해서 집을 방문하면 값을 0으로 바꾸는 방법을 사용했다.

간단한 그래프 탐색 문제이다.