백준 16928 [뱀과 사다리 게임] 파이썬 DFS BFS

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

맨 처음에는 위 문제를 dp를 이용해서 해결하려고 하였으나 실패하였다.

# 백준 16928 DFS
import sys
sys.setrecursionlimit = 10**6
N, M = map(int, input().split())
ladder = {}
snake = {}
for _ in range(N):
    a, b = map(int, input().split())
    ladder[a] = b
for _ in range(M):
    a, b = map(int, input().split())
    snake[a] = b
visited = [100000]*(101)
global answer
answer = 100000


def dfs(num):
    global answer
    if num == 100:
        answer = min(answer, visited[num])
    if num in ladder:
        if visited[ladder[num]] > visited[num]:
            visited[ladder[num]] = visited[num]
            dfs(ladder[num])
    elif num in snake:
        if visited[snake[num]] > visited[num]:
            visited[snake[num]] = visited[num]
            dfs(snake[num])
    else:
        for i in range(6, 0, -1):
            if num+i <= 100:
                if visited[num+i] > visited[num]+1:
                    visited[num+i] = visited[num]+1
                    dfs(num+i)


visited[1] = 0
dfs(1)
print(answer)

 

# 백준 16928 BFS
from collections import deque
import sys
N, M = map(int, input().split())
ladder = {}
snake = {}
for _ in range(N):
    a, b = map(int, input().split())
    ladder[a] = b
for _ in range(M):
    a, b = map(int, input().split())
    snake[a] = b
visited = [0]*(101)
global answer
answer = 100000
visited = [10000]*(101)


def bfs(num):
    global answer
    q = deque([])
    q.append(num)
    while q:
        num = q.popleft()
        if num == 100:
            answer = visited[100]
        else:
            if num in ladder:
                if visited[ladder[num]] > visited[num]:
                    visited[ladder[num]] = visited[num]
                    q.append(ladder[num])
            elif num in snake:
                if visited[snake[num]] > visited[num]:
                    visited[snake[num]] = visited[num]
                    q.append(snake[num])
            else:
                for i in range(6, 0, -1):
                    if num+i <= 100:
                        if visited[num+i] > visited[num]+1:
                            visited[num+i] = visited[num]+1
                            q.append(num+i)


visited[1] = 0
bfs(1)
print(answer)

DFS와 BFS의 원리는 같다. 그 점에서 최솟값을 갱신하면 계속 탐색하고, 그렇지 않다면 탐색을 멈추는 것이다.