백준 1012번: 유기농 배추

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론
• 깊이 우선 탐색 (DFS) 과 너비 우선 탐색 (BFS)
  
  

✔ 코드

import sys
from collections import deque

T = int(sys.stdin.readline())

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())

    box = [0] * (M*N)
    queue = deque([])
    stack = []

    for i in range(K):
        x, y = map(int, sys.stdin.readline().split())
        current = (M * y) + x
        box[current] = 1
        queue.append(current)

    count = 0
    while queue:
        tmp = queue.popleft()
        if box[tmp] == 1:
            stack.append(tmp)
            count += 1
        while stack:
            tmp = stack.pop()
            if tmp % M > 0:
                if box[tmp-1] == 1:
                    stack.append(tmp-1)
                    box[tmp-1] = 0
            if (tmp+1) % M > 0:
                if box[tmp+1] == 1:
                    stack.append(tmp+1)
                    box[tmp+1] = 0
            if tmp >= M:
                if box[tmp-M] == 1:
                    stack.append(tmp-M)
                    box[tmp-M] = 0
            if tmp < M*(N-1):
                if box[tmp+M] == 1:
                    stack.append(tmp+M)
                    box[tmp+M] = 0
    print(count)

• 이전에 풀었던 토마토 문제에서 좀만 더 생각하면 쉽게 풀 수 있다.
• 토마토 문제에서는 익은 토마토가 끊임 없이 주변 토마토를 익게 하기 때문에 맨 처음에 익어 있던 토마토와 나중에 익은 토마토를 같은 큐 (Queue) 안에서 관리했다.
• 하지만 이 문제는 서로 이어져 있는 연결 요소의 개수를 세는 쪽에 가까우므로 처음에 배추가 심어져 있는 위치들을 큐 (Queue)에 저장한 뒤, 하나씩 뽑아서 다시 스택 (Stack)에 넣고 DFS를 진행한다. (사실 BFS로 해도 무방하다. 해당 배추에서 지렁이가 옮겨갈 수 있는 곳들만 다 찾아내면 된다.)
• 이때, 이미 연결됐다고 판단한 배추는 값을 0으로 바꿔주어 하나의 연결 요소를 구성하는 위치들이 두 번 이상 큐에서 스택으로 들어가지 않도록 한다.

✔ 관련 개념

• 그래프 (Graph) 이론과 그래프 탐색 (DFS, BFS)