[BOJ] 1012 유기농 배추 - python

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

 

'11724 연결 요소의 개수 문제'와 '13565 침투' 문제를 합친 문제 같았다.

실제로도 위 두 문제를 합치니 해결이 가능했다.

 

dfs를 이용하여 더 이상 재귀를 불러올 수 없을 경우 count를 증가시켜주는 방식으로 풀었다.

나는 행렬 형태에 입력 값을 넣었는데, 백준에서 그려놓은 그림과 같이 입력을 받으려면

입력받는 x,y 값과 행렬을 호출하는 x,y값이 반대라는 것을 주의해야한다.

 

행렬 호출 값과 입력 값의 차이

 

import sys
sys.setrecursionlimit(1000000)

T = int(sys.stdin.readline())

def dfs(x,y):
    if x <= -1 or x >= N or y <= -1 or y >= M:		# x,y가 접근 불가한 값이면 
        return
    elif graph[x][y] == 1 and visited[x][y] == 0:	# 행렬이 접근 가능한 곳이고, 방문한 적이 없으면
        visited[x][y] = 1
        dfs(x,y-1)
        dfs(x-1,y)
        dfs(x,y+1)
        dfs(x+1,y)

for _ in range(T):
	# M: 가로의 길이 / N: 세로의 길이 / K: 배추의 개수(=1의 개수)
    M, N, K = map(int,sys.stdin.readline().split())

    visited = [[0]*(M) for _ in range(N)] 
    graph = [[0]*(M) for _ in range(N)]

    for i in range(K): 
        a, b = map(int, sys.stdin.readline().split()) 
        graph[b][a] = 1  

    count = 0
    for x in range(N):
        for y in range(M):
            if visited[x][y] == 0 and graph[x][y] == 1:
                dfs(x,y)		# 더 이상 재귀를 호출할 수 없으면(= 인접 노드 중 더 이상 방문 가능한 곳이 없으면)
                count += 1		# count를 증가
            
    print(count)