[BOJ][Python]백준 1012 풀이

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

1012번: 유기농 배추

import sys
sys.setrecursionlimit(10**6)
ssr = sys.stdin.readline

def sol(x,y):
    if x<0 or x>=m or y<0 or y>=n:
        return
    if farm[x][y] == 0:
        return
    farm[x][y]=0
    sol(x-1,y)
    sol(x+1,y)
    sol(x,y-1)
    sol(x,y+1)

t = int(ssr())
for _ in range(t):
    m,n,k = map(int,ssr().split())
    farm = [[0 for _ in range(n)] for _ in range(m)]
    bug=0
    for _ in range(k):
        x,y = map(int, ssr().split())
        farm[x][y] = 1
    for i in range(m):
        for j in range(n):
            if farm[i][j] == 1:
                sol(i,j)
                bug += 1
    print(bug)

재귀를 이용해서 문제를 해결하시면 탐색을 엄청 하기 때문에 제한에 걸려요. sys.setrecursionlimit(10**6)이 부분을 빠뜨리지 말고 넣어 주셔야 합니다. 사실 저도 dfs는 공부를 하고 있는 입장이라 뭐라고 잘 설명하기가 참 어려운데요. 일단 해당 문제를 푸는데 사용한 개념은 배추가 심어져있는 부분 즉, 1인 부분을 찾아서 주변에 1이 없어질때까지 탐색을 진행하고(탐색을 한 부분은 0으로 바꿔서 또 탐색하는 것을 방지합니다), 탐색이 완료되면 배추흰지렁이의 갯수를 하나 올림으로 끝이나도록 하는 것입니다. 인접한 부분은 지렁이 한 마리만 필요하기 때문에 동서남북 네방향에 인접한게 있는지를 체크하기위해 재귀를 사용하는 것이구요. 주의하셔야할 부분은 배열의 행과 열의 갯수일까요. 저도 중간에 한 번 헷갈리는 바람에 인덱스 에러가 많이 떴거든요.

 

언제든지 댓글로 궁금한게 있으시면 물어보셔도 됩니다.