[백준] 1743 - 음식물 피하기 (Python)

[백준] 1743 - 음식물 피하기

• https://www.acmicpc.net/problem/1743
• 알고리즘:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색
  • 깊이 우선 탐색

풀이 - DFS

import sys
sys.setrecursionlimit(10**7) #재귀 깊이 설정

N,M,T=map(int, input().split())
arr=[[0]*M for _ in range(N)]
visited=[[0]*M for _ in range(N)]
answer=[]

dx=[-1,1,0,0] #상,하,좌,우
dy=[0,0,-1,1] #상,하,좌,우

for i in range(T):
    a,b=map(int, input().split())
    arr[a-1][b-1]=1

def dfs(x,y):
    global num
    num+=1
    visited[x][y]=1
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=0 and nx<N and ny>=0 and ny<M:
            if arr[nx][ny]==1 and visited[nx][ny]==0:
                dfs(nx,ny)
    return num

for i in range(N):
    for j in range(M):
        if arr[i][j]==1 and visited[i][j]==0:
            num=0
            answer.append(dfs(i,j))

print(max(answer))

📌 sys.setrecursionlimit() 사용

파이썬 최대 재귀 횟수는 1000번으로 제한되어 있어서 DFS문제를 풀때 런타임 에러가 발생할 수 있으므로 재귀 제한을 풀어주어야 한다.

• algorithms