[백준-16928] 뱀과 사다리 게임

이말감·2022년 3월 9일
0

문제

링크

코드

from collections import deque

n, m = map(int, input().split())

graph = [0] * 101
visited = [0] * 101
for _ in range(n+m) :
    a, b = map(int, input().split())
    graph[a] = b

queue = deque([1])
visited[1] = 0
while queue:
    n = queue.popleft()
    if n == 100 :
        print(visited[n])
        break
    for i in range(1,7) :
        if n+i <= 100 and visited[n+i] == 0:
            nxt = n+i
            if graph[nxt] != 0 :
                nxt = graph[nxt]
            if visited[nxt] == 0 :
                queue.append(nxt)
                visited[nxt] = visited[n] + 1

풀이

BFS를 이용해서 풀었다. 테스트케이스는 맞는데 제출했을 때 계속 틀렸다고 해서 다른 사람들의 코드를 참고했다.
문제를 잘 이해하지 못하여 틀렸던 것이다.
그래서 아래와 같이 풀이하여 풀 수 있었다.

  • 풀이
  1. 1부터 시작한다.
  2. n이 100이 되면 종료
  3. 주사위를 굴려서 (1~6) 더한 후, 해당 값이 100 이하인지, 방문 여부를 확인한다.
    3-1. 사다리나 뱀이 있는지 확인하고, 있다면 해당 번호로 이동한다.
  4. 번호는 n이고 다시 2번으로 이동.
profile
전 척척학사지만 말하는 감자에요

0개의 댓글