[ 그래프 이론-1012 ] 유기농 배추(Python)

1012번 유기농 배추

---

접근법

처음에는 배추가 심어진 것을 표현하기 위한 MxN Matrix와 해당 위치에 방문한 것을 확인하기 위한 추가적인 배열을 생성해 푸는 방향으로 접근하였다. 

하지만 위 방법으로 접근하면 무수히 많은 if문과 필요한 배추흰지렁이마리수 즉, 1이 상/하/좌/우로 붙어져 있는 경우 count를 하기에 매우 비효율적이다.

 

따라서 주변에 배추가 심어져 있는지 확인하는 함수를 추가적으로 생성 후 해당 함수 실행 시 count를 한다. 

해당 함수 내에서는 상하좌우의 위치에 접근하여 1인지 확인 후 1이면은 0으로 바꾸는 방식으로 인접 배추들에 대한 방문을 확인하여, dfs 방식으로 접근하다.

 

---

정답

import sys
sys.setrecursionlimit(10000)

def check(x,y):
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    
    for i in range(4):
        X = x + dx[i]
        Y = y + dy[i]
        if( 0 <= X < M and 0<= Y < N):
            if land[Y][X] == 1:
                land[Y][X] = 0
                check(X,Y)
        

t = int(input())

for i in range(t):
    M, N, T = map(int, sys.stdin.readline().split())
    
    land = [[0]*(M) for _ in range(N)]
    cnt = 0
    
    for _ in range(T):
        x,y = map(int, sys.stdin.readline().split())
        land[y][x] = 1
    
    for x in range(M):
        for y in range(N):
            if land[y][x] == 1:
                check(x,y)
                cnt += 1
        
    print(cnt)

 

만약 재귀를 사용하여 문제를 해결해야 하는 경우 

import sys
sys.setrecursionlimit(10000)

 

이것을 꼭 해줘야 한다.

이는 파이썬에서 기본 재귀 깊이의 경우 매우 작기 때문에 추가적으로 설정 해 주지 않으면 런타임 에러를 발생시킬 수 있다. 기본적으로 10*6을 인자로 한다고 한다.

 

입력값을 모두 받아서 land 2차원 array에 저장한 후 해당 위치가 1인 경우 cnt를 증가시키고 check()를 실행시킨다.

def check(x,y):
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    
    for i in range(4):
        X = x + dx[i]
        Y = y + dy[i]
        if( 0 <= X < M and 0<= Y < N):
            if land[Y][X] == 1:
                land[Y][X] = 0
                check(X,Y)

 

dx,dy를 설정 한 이유는 상하좌우로 연결되어 있는 배추들은 모두 인접한 것으로 해야하기 때문에 for문을 돌면서 각각의 움직임을 표현하기 위해서이다.

또한, if문 안에서 단순히 X<M, Y<N 으로만 조건을 거는 경우 index error를 발생시킬 수 있다.

 

만약 해당 위치에 배추가 존재한다면 0으로 설정한 후 다시 재귀적으로 함수를 호출하여 최소한의 필요한 배추흰지렁이 수를 계산한다.