1012 - 유기농 배추

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

1012번: 유기농 배추

 

- DFS

 

import sys

sys.setrecursionlimit(int(1e9))
input = sys.stdin.readline

def dfs(dy, dx):
    if dy <= -1 or dx <= -1 or dy >= n or dx >= m:
        return

    if matrix[dy][dx]:
        matrix[dy][dx] = 0
        
        dfs(dy+1,dx)
        dfs(dy-1,dx)
        dfs(dy,dx+1)
        dfs(dy,dx-1)
    else:
        return


t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())

    matrix = [[0] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        matrix[y][x] = 1

    cnt = 0
    for x in range(m):
        for y in range(n):
            if matrix[y][x] == 1:
                dfs(y,x)
                cnt += 1

    print(cnt)

 

좌표 하나를 찍고 그 좌표에서 탐색 연산을 진행!

탐색한 부분의 값을 0으로 만들어주고, 상하좌우에 1이 없으면 탐색 연산을 종료시킨다

 

다음 좌표로 이동하는데, 만약 값이 0이면 탐색 연산을 진행하지 않고 skip

 

dfs 연산의 횟수를 출력하면 정답이다

 

 

DFS로 구현한 이유는 쉬워서..ㅎ

DFS를 응용한 풀이를 해서 기분이 좋다