[Python] 백준 1012 유기농 배추 (DFS)

 

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

문제분석

이전에 푼 문제중 이와 비슷한 문제가 있었다.

배추가 묶인 덩어리들의 갯수가 몇개인지 구하는 것이다.

해결과정

DFS를 이용하였다. 현재로써 나에겐 DFS를 직접 의도해서 구현 후 해결한 몇 안되는 문제이다.

 

처음에는, 해당하는 배추 좌 우에 다른 배추가 있으면 숫자를 조절하는 방식으로 진행하려 했다.

그러나 이 방식에는, (기존 배추) - 배추 - (기존 배추)로 연결이 되는걸 커버하지 못한다.

따라서 dfs를 활용해서, 덩어리의 갯수를 직접적으로 세기로 했다.

arr에 저장한 후, 이 arr에서 첫번째 배추를 기준으로 재귀 dfs를 실행한다.

이는 while을 통해서 arr이 0이 될 때까지 반복된다.

 

문제에서, 좌표(배추농장)의 가로세로 길이를 게종하는데, 이는 굳이 필요한 정보인것 같지는 않다

(꼭 필요하다면 배추 좌표의 최대값을 농장의 끝으로 봐도 무방하지 않나..?)

import sys
sys.setrecursionlimit(10**6)
T=int(input())

def dfs(target):
    # 사방위에 배추가 있는지 확인하고, 있으면 그 지점에서 다시 dfs 작동
    global arr
    targetarr=[[target[0]+1,target[1]],[target[0],target[1]+1]
                   ,[target[0]-1,target[1]],[target[0],target[1]-1]]
    arr.remove(target)
    for i in targetarr:
        if i in arr: # 그 방향에 배추가 존재한다면
            dfs(i)
    
arr=[] # 검증하기 전 배추들 저장
count=0
for _ in range(T):
    arr=[]
    end=[]
    count=0
    _,_,K=map(int, input().split())
    for i in range(K):
        temp=list(map(int,input().split()))
        arr.append(temp)
    arr.sort(key=lambda x:(x[0],x[1]))
    while arr:
        dfs(arr[0])
        count+=1
    print(count)