백준 1012번 유기농 배추

오늘은 백준 1012번 문제 유기농 배추 문제를 풀어보았다. 해당 문제를 보고 고민하다가 많은 시간을 고민하여도 해결되지 않아서 패스트캠퍼스 강의를 참조하여 많은 깨달음을 얻었다.

 

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

1012번: 유기농 배추

import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    visited[x][y] = True
    directions = [(-1,0),(1,0), (0,-1), (0,1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx,ny)

for _ in range(int(input())):
    m, n, k = map(int, input().split())
    array = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                dfs(i, j)
                result += 1
    print(result)

위 코드를 활용해 답을 구하였다. 재밌는 점은 directions 리스트의 하나의 값에 x와 y 좌표를 담아 두었다. 그리고 for문을 돌면서 x,y좌표에 값을 더해서 돌도록 만들엇고 값의 범위가 올바른지 그리고 방문하지 않았던 좌표인지 그리고 벌레가 방문 할 수 있는 좌표인지 검증을 통해 dfs함수를 다시 호출한다. 해당 문제를 풀면서 dfs문제의 핵심이라 해도 될 정도로 중요한 문제라고 느꼈고 가끔식 복습해야겠다