글 읽기 - bfs(반복문), dfs(재귀) 코드 속도 차이 질문드립니다!

dmltls94 2년 전 0

혹시 제가 알기로는 dfs(재귀)보다 bfs(반복문)이 훨씬 빠르다고 알고있는데 이 문제는 왜 dfs는 정답판정나고

bfs는 70%에서 왜 시간초과 날까요? 똑같은 코드인데 말이죠 ㅠ 알려주시면 정말 감사하겠습니다.

#통과하는 코드입니다. dfs입니다.
import sys
input = sys.stdin.readline
n = int(input().strip())
board = []
for i in range(n):
    board.append(list(map(int, input().strip().split())))
#0가로 1세로 2대각
result = 0
def dfs(x2,y2,d):
    global result
    if x2 == n-1 and y2 == n-1:
            result += 1
    if d == 0 or d == 2:
        ny2 = y2 + 1
        if ny2 < n and board[x2][ny2] == 0:
            dfs(x2, ny2, 0)

    if d == 1 or d ==2:
        nx2 = x2 + 1
        if nx2 < n and board[nx2][y2] == 0:
            dfs(nx2, y2, 1)
    nx2 =x2 + 1
    ny2 = y2 +1
    if nx2 < n and ny2 < n and board[nx2][ny2] == 0 and board[nx2][ny2 - 1] == 0 and board[nx2 - 1][ny2] == 0:
        dfs(nx2, ny2, 2)

if board[n-1][n-1] == 1:
    print(0)
else:
    dfs(0,1,0)
    print(result)
    
    
#70%에서 시간초과판정나는 코드입니다.
import sys
from collections import deque
input = sys.stdin.readline
n = int(input().strip())
board = []
for i in range(n):
    board.append(list(map(int, input().strip().split())))
#0가로 1세로 2대각
def bfs():
    result = 0
    q = deque()
    q.append((0, 1, 0))
    while q:
        x2, y2, d = q.popleft()
        if x2 == n-1 and y2 == n-1:
            result += 1
            continue
        if d == 0 or d == 2:
            ny2 = y2 + 1
            if ny2 < n and board[x2][ny2] == 0:
                q.append((x2, ny2, 0))

        if d == 1 or d ==2:
            nx2 = x2 + 1
            if nx2 < n and board[nx2][y2] == 0:
                q.append((nx2, y2, 1))
        nx2 =x2 + 1
        ny2 = y2 +1
        if nx2 < n and ny2 < n and board[nx2][ny2] == 0 and board[nx2][ny2 - 1] == 0 and board[nx2 - 1][ny2] == 0:
            q.append((nx2, ny2, 2))
    print(result)
if board[n-1][n-1] == 1:
    print(0)
else:
    bfs()

azaraks 2년 전 1

dfs(재귀)보다 bfs(반복문)이 훨씬 빠르다고 알고있는데

아닙니다.

djunnni 1년 전 0

저는 자바로 dfs로 푸니 정답이 나오고 bfs로 풀땐 88%정도에서 죽더라구요

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

문제

문제

출처

ICPC

bfs(반복문), dfs(재귀) 코드 속도 차이 질문드립니다!

dmltls94 2년 전 0

azaraks 2년 전 1

djunnni 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말