📌 [BOJ] 백준 1012 유기농 배추

📖 문제

📖 예제

📖 풀이

DFS

import sys
sys.setrecursionlimit(10000000)

T = int(input())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(T):
  M, N, K =  map(int, sys.stdin.readline().split())
  graph = [[0]*M for _ in range(N)]
  for _ in range(K):
    a, b = map(int, sys.stdin.readline().split())
    graph[b][a] = 1

  def DFS(x,y):
    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>=M:
        continue
      if graph[nx][ny] == 1:
        DFS(nx,ny)
    


  cnt = 0
  for i in range(N):
    for j in range(M):
      if graph[i][j] == 1:
        DFS(i,j)
        cnt += 1

  print(cnt)

BFS

from collections import deque
import sys
sys.setrecursionlimit(10000000)

T = int(input())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(T):
  M, N, K =  map(int, sys.stdin.readline().split())
  graph = [[0]*M for _ in range(N)]
  for _ in range(K):
    a, b = map(int, sys.stdin.readline().split())
    graph[b][a] = 1

  def BFS(x,y):
    graph[x][y] = 0
    queue = deque()
    queue.append((x,y))
    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>=M:
          continue
        if graph[nx][ny] == 1:
          graph[nx][ny] = 0
          queue.append((nx,ny))
    


  cnt = 0
  for i in range(N):
    for j in range(M):
      if graph[i][j] == 1:
        BFS(i,j)
        cnt += 1

  print(cnt)

입력된 그래프에서 DFS/BFS을 진행한 횟수를 출력한다.