[BOJ] 유기농 배추

---

코드

from sys import stdin
from collections import deque
import sys
input = stdin.readline

T = int(input())

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

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    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))
    return

for _ in range(T):
    cnt = 0
    N, M, K = map(int, input().split())
    graph = [[0]*M for _ in range(N)]
    
    for _ in range(K):
        i, j = map(int, input().split())
        graph[i][j] = 1
    
    for i in range(N):
        for j in range(M):
            if(graph[i][j] == 1):
                bfs(graph, i, j)
                cnt += 1
    print(cnt)

결과

풀이 방법

• BFS를 활용하는 문제
• 땅의 각 좌표를 방문하다가 1인 땅을 발견할 때마다 해당 땅을 기준으로 BFS를 수행한다. BFS를 수행하면서 방문하는 1은 방문한 다음 0으로 바꾼다.
• BFS가 한 번 수행될 때마다 인접한 1들의 구역을 하나 찾은 것이므로 cnt를 1씩 증가시킨다
• BFS, DFS 문제는 해당 알고리즘을 구현하는 방법을 숙지해두자

---