문제

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

간단하게 뱀과 사다리를 타고 100의 위치에 가야하는 게임이고, 주사위를 최소 몇번 던져야하는지 묻는 문제이다

문제의 유형에서 BFS가 적혀있었고, 다른사람도 BFS로 풀었는데, 나는 DFS로 풀었다.

주요 아이디어는 뱀이나 사다리 같은 특징점을 잡고,
그 특징점을 선택할 것인지 말것인지를 경우를 나눠 트래킹 하는 방식이다.

min_throw 함수의 경우, bfs를 통해 갈수 있는 최단거리를 구했고, 이 함수에서는 뱀이나 사다리를 무조건 제외하도록 하였다.

나의 풀이

import sys


# 현재 위치에서 저 위치에 도착하는데 최소 주사위 던지는 횟수
# 사다리 밟지 않고 뱀도 밟지 않고
# bfs
def min_throw(current_pos, dest_pos):
    count = 0
    q = []
    q.append(current_pos)

    while q:
        count += 1
        for _ in range(len(q)):
            pos = q.pop(0)
            # 목적지까지 6칸 이내면, 조기 종료
            if dest_pos - pos <= 6:
                return count  # 종료 조건
            for i in range(6, 0, -1):
                # 사다리 칸이면, 무조건 거부
                np = pos + i
                if np in LI:
                    continue
                # 일반 칸이면, 이동
                q.append(np)
                break
    # 여기 까지 왔으면, 절대 못가는거
    return -1


def dfs(count, pos):
    global ans
    if count > ans:
        return
    f = list(filter(lambda x: x[0] > pos and not (x in visited), L))

    # 링크 이용을 안하는 경우
    # 100까지 직진하라는 말
    d = min_throw(pos, 100)
    if d != -1:  # -1이면 절대 못가는거
        ans = min(ans, count + min_throw(pos, 100))

    for link in f:
        # 저기로 이동한다는 뜻
        d = min_throw(pos, link[0])
        if d == -1:
            continue
        visited.add(link)
        dfs(count + d, link[1])
        visited.remove(link)


# input
N, M = map(int, input().split())

L = [tuple(map(int, input().split())) for _ in range(N + M)]
LI = set()
for i in L:
    LI.add(i[0])

ans = sys.maxsize
visited = set()

dfs(0, 1)
print(ans)