[백준] 1012번 유기농 배추(DFS 알고리즘)(Python - 파이썬)

백준  1012번 문제입니다.  (solved.ac)기준  실버 2 문제입니다.

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

1012번: 유기농 배추

예제 입력 1 :                                                    

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

    예제 출력 1 :

5
1

 

첫번째 줄에는 테스트 케이스 T를 입력하고

( //로 감싸여 있는 세 줄은 테스트 케이스(T)만큼 반복합니다.)

// 두번째 줄에는 배추를 심은 배추밭의 가로길이 M, 세로길이 N, 배추가 심어진 위치의 개수 K를 입력합니다.

범위는 (1 <= M, N <= 50) / (1 <= K <= 2500) 입니다.

세번째 줄 부터는 K번 반복하여 배추의 위치 X(0 <= X <= M-1) , Y(0 <= Y <= N-1) 를 입력합니다. //

 

문제에서 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 필요하다고 알려주었기 때문에 저는 이 문제를 배추가 있는 곳을 탐색할 때 인접한 배추들을 확인한 후 묶고(인접한 배추들 모두 1 -> 0으로 변환하여 다음 탐색 간에는 넘어갈 수 있도록) 그 배추 묶음당 필요한 배추흰지렁이가 1마리씩 증가하는 식의 방법으로 접근하였습니다.

[백준] 2267번 문제인 단지번호붙이기와 동일한 방식(DFS 알고리즘)으로 문제에 접근하였습니다.

[알고리즘 문제풀이] - [백준] 2667번 단지번호붙이기(DFS알고리즘)(Python)

'''
T는 테스트 케이스의 개수
M, N, K는 각각 배추밭의 가로길이(M), 세로길이(N), 배추가 심어져 있는 위치의 개수(K)
'''

import sys
# 재귀 호출 최대 횟수 늘려주기
sys.setrecursionlimit(10**7)
T = int(sys.stdin.readline().rstrip()) 

# 필요한 배추흰지렁이의 수를 담을 변수
# 인접해 있는 배추들을 확인 및 묶은 후 배추묶음 당
# 필요한 배추흰마리 1마리 증가 
cnt = 0 
	

def dfs(x, y):

    # 범위를 넘어가면 즉시 탐색 종료
    if x <= -1 or x >= N or y <= -1 or y >= M:
        return False
	
    # 배추가 있는 곳(1)이라면 확인(방문)했다는 의미로 0으로 변경
    # 주변(상,하,좌,우)도 배추가 있는지 확인
    # 주변에도 배추가 있다면 그 배추또한 0으로 값을 변경(반복)
    # 주변의 배추들을 모두 확인하는(1 -> 0)과정을 통하여
    # 인접해있는 배추들 모두 0으로 바꾸어(방문판정)
    # 다음 탐색간에는 False를 반환하여
    # 한 번만 True값을 반환하게 해줌.
    if graph[x][y] == 1:
        graph[x][y] = 0

        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        # True반환당 배추흰지렁이(cnt) 1 증가
        return True

    return False

# 테스트 케이스(T)만큼 반복
for _ in range(T):

    M, N, K = map(int,sys.stdin.readline().rstrip().split())

    # 리스트 컴프리핸션으로 2차원 리스트 모두 0으로 초기화
    graph = [[0] * (M) for _ in range(N)]

    # 배추가 심어져 있는 위치의 개수(k) 만큼 배추를 심음
    # 위치를 입력 받아 그 위치의 0 을 1로 변경
    for _ in range(K) :
        x, y = map(int, sys.stdin.readline().rstrip().split())
        graph[y][x] = 1
        
 	'''아래와 같이 2차원 리스트를 생성
 	[
 	[1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
 	[0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
 	[0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
 	[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
 	[0, 0, 1, 1, 0, 0, 0, 1, 1, 1], 
 	[0, 0, 0, 0, 1, 0, 0, 1, 1, 1], 
 	[0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 
 	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 	]
 	'''

    # 범위를 탐색하며 배추묶음(인접한 배추들) 당
    # 필요 배추흰지렁이(cnt)값 1 증가
    for i in range(N) :
        for j in range(M) :
            if dfs(i,j) == True :
                cnt += 1

    print(cnt)
    # 다음 테스트 케이스(T)의 필요 배추흰지렁이(cnt)는 처음부터 세야하므로 
    # 필요 배추흰지렁이(cnt)는 0으로 초기화
    cnt = 0