1012번. 유기농 배추

https://www.acmicpc.net/problem/1012

 

 

 

BFS와 DFS를 이해하고

2667번을 풀어봤다면 오히려 더 쉬운 문제이지만,

m와 n, x와 y, 가로와 세로, 행과 열에 있어서 헷갈렸던 문제...

import sys


def DFS(row, col):
    stack = []
    stack.append([row, col])

    while stack:
        r, c = stack.pop()
        if visited[r][c] == 0:
            visited[r][c] = 1
            for nR, nC in [[r+1, c],[r-1,c],[r,c+1],[r,c-1]]:
                if 0 <= nR < n and 0 <= nC < m:
                    if farm[nR][nC] == 1:
                        stack.append([nR, nC])


T = int(sys.stdin.readline())   # 테스트케이스 갯수

for _ in range(T):
    m, n, k = map(int, sys.stdin.readline().split())   # 가로, 세로, 배추갯수
    farm = [[0 for _ in range(m)] for _ in range(n)]
    visited = [[0 for _ in range(m)] for _ in range(n)]  # 배추벌레가 방문한 곳
    worm = 0  # 배추벌레의 갯수 카운트

    for _ in range(k):
        col, row = map(int, sys.stdin.readline().split())
        farm[row][col] = 1  # 배추가 위치하는 곳을 1로 표시

    #print(farm)
    for row in range(n):
        for col in range(m):
            if farm[row][col] == 1 and visited[row][col] == 0:
                DFS(row, col)
                worm += 1

    print(worm)