📌 [BOJ] 백준 2667 단지번호붙이기

📖 문제

📖 예제

📖 풀이

DFS

N = int(input())
graph = []
for _ in range(N):
  graph.append(list(map(int, input())))

dx = [1,-1,0,0]
dy = [0,0,1,-1]
answer = []
cnt = 0
def DFS(x,y):
  global cnt
  cnt += 1
  graph[x][y] = 0
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if nx<0 or nx>=N or ny<0 or ny>=N:
      continue
    if graph[nx][ny] == 1:
      DFS(nx,ny)

for i in range(N):
  for j in range(N):
    if graph[i][j] == 1:
      DFS(i,j)
      answer.append(cnt)
      cnt = 0
      
print(len(answer))
for i in sorted(answer):
  print(i)

BFS

from collections import deque

N = int(input())
graph = []
for _ in range(N):
  graph.append(list(map(int, input())))

dx = [1,-1,0,0]
dy = [0,0,1,-1]
answer = []
cnt = 0
def BFS(x,y):
  queue = deque()
  queue.append((x,y))
  graph[x][y] = 0
  global cnt
  cnt += 1
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if nx<0 or nx>=N or ny<0 or ny>=N:
        continue
      if graph[nx][ny] == 1:
        graph[nx][ny] = 0
        queue.append((nx,ny))
        cnt += 1

for i in range(N):
  for j in range(N):
    if graph[i][j] == 1:
      BFS(i,j)
      answer.append(cnt)
      cnt = 0
      
print(len(answer))
for i in sorted(answer):
  print(i)

그래프 내에서 1의 값을 갖는 위치를 찾아 DFS/BFS을 통해 본인을 포함한 1의 값을 갖는 주변 그래프 위치의 갯수를 따로 저장한 후 마지막에 저장된 값의 갯수와 저장된 값의 오름차순을 출력한다.