[python 파이썬] 백준 1012번 유기농배추

1012번: 유기농 배추

 

이 문제는 보아하니 2667번 단지번호붙이기할 때 참고했던 음료수 얼려먹기문제(DFS)와 유사했다. 

2667번 문제풀이링크를 참고하겠다.

[python 파이썬] 백준 2667번 단지번호붙이기

음료수 얼려먹기 문제와 다른 점은 테스트케이스가 있는 점과 입력형식인데 그 부분만 수정해주면 해결이 되었다. 

 

또한 맞게 풀고 테스트해보니 런타임에러(RecursionError)가 떴다. 이걸 해결하기 위해서는 호출을 제한하는 함수를 호출해야한다.-파이썬에서 DFS BFS풀때 런타임에러를 만난다면 적용해주자 

 

(재귀함수의 최대 재귀 깊이를 수동으로 늘려주는 코드)

import sys
sys.setrecursionlimit(10**8)

 

또한 출력형식이 잘 맞지않아서 결과를 result라는 리스트에 담고 for문으로 출력하도록 했다. 

 

import sys
sys.setrecursionlimit(10**8) #재귀제한높이설정(기본값이상으로 안해주면 런타임에러) ※기본값:1000
def dfs(x,y):
    #주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재노드를 아직 방문하지 않았다면
    if graph[x][y]==1:
        #해당노드 방문처리
        graph[x][y]=0
        #상하좌우의 위치도 모두 재귀적으로 호출
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)

        return True
    return False

def solve():
    result=0
    for i in range(n):
        for j in range(m):
            #현재위치에서 dfs수행
            if dfs(i,j)==True:
                result+=1
    print(result)

result=[]
t = int(input())
for tt in range(t):
    n,m,k=map(int,input().split())

    graph=[[0]*m for i in range(n)]

    #배추밭채우기
    for _ in range(k):
        x,y=map(int,input().split()) #y x ?

        graph[x][y]=1

    count=0
    for i in range(n):
        for j in range(m):
            #현재위치에서 dfs수행
            if dfs(i,j)==True:
                count+=1
    result.append(count)
for r in result:
    print(r)

 

참고 

2차원리스트 0으로 초기화하는 방법

limseee.blogspot.com/2016/06/2-0.html

[파이썬] 2차원 리스트 0으로 초기화 하는 방법