글 읽기 - BFS로 풀었을 때는 잘 되는데 DFS로 풀었을 때 런타임에러가 납니다...

jhkim990212 1년 전 0

BFS로 풀었을 때는 잘 되는데 DFS로 풀었을 때 런타임에러가 납니다...

import sys
from collections import defaultdict
input = sys.stdin.readline

w, h = map(int, input().split())
inpHome = defaultdict(list)
for i in range(h):
    inpHome[i].extend(list(map(int, input().split())))
home = [[0]*(w+2) for _ in range(h+2)]
for y in range(h):
    for x in range(w):
        home[y+1][x+1] = inpHome[y][x]

ans = 0
visited = [[False] * (w+2) for _ in range(h+2)]

def dfs(x, y):
    global ans
    if x<0 or y<0 or x>w+1 or y>h+1:
        return
    if home[y][x] == 1:
        ans += 1
    elif home[y][x] == 0 and visited[y][x] == False:
        visited[y][x] = True
        if y % 2 == 1:
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x+1, y-1)
            dfs(x, y+1)
            dfs(x+1, y+1)
        else:
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x-1, y-1)
            dfs(x, y-1)
            dfs(x-1, y+1)
            dfs(x, y+1)
            
dfs(0, 0)
print(ans)

siyamaki 1년 전 1

W와 H가 100 by 100에 모든 값이 1일때를 생각해보세요..

jhkim990212 1년 전 0

W와 H가 100 by 100에 모든 값이 1일때를 생각해보세요..

문제가 없는 것 같습니다... 이해가 안되네요 ㅎㅎ..ㅠ

siyamaki 1년 전 1

파이썬의 기본 재귀는 1000회가 끝입니다. 그 이상으로 들어가면 강제 런타임 에러를 발생시킵니다.

sys.setrecursionlimit(10**6)을 설정해서 재귀의 제한을 늘릴 수 있지만 map을 탐색하는 과정에서는 부적절해 보입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS로 풀었을 때는 잘 되는데 DFS로 풀었을 때 런타임에러가 납니다...

jhkim990212 1년 전 0

siyamaki 1년 전 1

jhkim990212 1년 전 0

siyamaki 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말