[16928번] 뱀과 사다리 게임

백준 16928번 뱀과 사다리 게임

코드 풀이

• 현재 칸이 이동할 수 있는 경우의 수는 자신의 칸에서 +1 ~ +6입니다.
• 뱀과 사다리가 연결된 칸을 만났을 경우 연결된 칸으로만 이동할 수 있습니다.
• 각 칸에서 갈 수 있는 경우의 수를 그래프로 묶고, DFS 방식을 적용해 해결할 수 있습니다.
• cost 변수에는 해당 칸에 도달할 수 있는 최소 경우의 수가 입력됩니다.
• 해당 칸을 한 번도 방문하지 않았거나, 방문할 예정인 칸에 적힌 cost의 값이 현재 칸에서 이동하는 경우의 수보다 크다면, cost값을 갱신합니다(if문).

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, sys.stdin.readline().split(' '))

graph = [[] for _ in range(100+1)]
short_cut = []   # 뱀, 사다리가 놓여진 시작 칸
for _ in range(n+m):
    x, y = map(int, sys.stdin.readline().split(' '))
    graph[x].append(y)
    short_cut.append(x)

for i in range(1, 100+1):
	# 뱀, 사다리가 놓여진 시작 칸일 경우 +1 ~ +6으로 이동할 수 없음.
    if i in short_cut:
        continue
    for j in range(1, 6+1):
        if i+j <= 100:
            graph[i].append(i+j)

#print(graph)

# 인덱스는 칸 번호를 나타내고, 각 칸에 도달할 수 있는 최소 경우의 수가 들어감.
cost = [0] * (100+1)
#print(cost)


def dfs(x, cnt):
    cost[x] = cnt
    # 뱀, 사다리를 만났을 경우, 바로 이동하기 때문에 이동 횟수가 추가되지 않음.
    if x in short_cut:
        cnt -= 1
    for i in graph[x]:
        if not cost[i] or cost[i] > cnt + 1:
            dfs(i, cnt+1)


dfs(1, 0)
print(cost[100])