백준 1012번: 유기농 배추

백준 1012번: 유기농 배추

아이디어

그래프의 연결 요소 개수를 세면 된다. 배추가 위치한 좌표를 dfs 함수에 넣었을 때 True를 반환하면 처음 방문한 배추이고 False를 반환하면 이전에 방문한 적이 있는 배추이다.
True를 반환하는 횟수가 정답이다.

코드

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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


def dfs(graph, visited, row, col):
    if visited[row][col] is True or graph[row][col] == 0:
        return False
    visited[row][col] = True
    for i in range(4):
        ny = row + dy[i]
        nx = col + dx[i]
        if 0 <= ny < N and 0 <= nx < M:
            dfs(graph, visited, ny, nx)
    return True


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    graph = [[0]*M for _ in range(N)]
    visited = [[False]*M for _ in range(N)]
    cabbages = []
    cnt = 0
    for _ in range(K):
        X, Y = map(int, input().split())
        graph[Y][X] = 1
        cabbages.append([Y, X])
    for i in cabbages:
        if dfs(graph, visited, i[0], i[1]):
            cnt += 1
    print(cnt)

여담

BFS로도 풀 수 있는데 나중에 한 번 풀어봐야할듯. 처음엔 배추흰지렁이가 이동할 수 있는 거리가 딱 한 칸인줄 알고 머리를 싸맸다.