[백준] 1012번 문제 (유기농 배추) 파이썬(Python) 풀이

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

1012번: 유기농 배추

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def dfs(i, j):
    if i < 0 or i >= n or j < 0 or j >= m or mtx[i][j] == 0:
        return
    mtx[i][j] = 0

    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())
    mtx = [[0] * m for _ in range(n)]

    for _ in range(k):
        x, y = map(int, input().split())
        mtx[y][x] = 1

    count = 0

    for i in range(n):
        for j in range(m):
            if mtx[i][j] == 1:
                dfs(i, j)
                count += 1

    print(count)

처음에는 bfs로 접근해서 풀었으나 시간 초과가 났다.. (아마 bfs로도 풀릴텐데 최적화의 문제가 있었던 것 같다.)

그래서 바로 dfs로 접근해서 문제를 제출했고, 어렵지 않게 풀 수 있었다.

 

문제의 핵심은 배추가 몇 개의 구역으로 나뉘어져 있는지 파악하는 것이다.

 

우선 2차원 배열 형태로 배추가 있는 곳을 파악하고, 

dfs를 재귀 형태로 사용해서 탐색의 범위를 넓혀가며 배추의 구역을 파악하면 배추 구역의 개수를 알 수 있다.