백준 16928번 사다리와 뱀 게임

많이 헤맸던 문제로 방문 처리나 사다리 뱀 타는 것의 유무등 헷갈리는 것이 많아서 시간을 많이 소요했던 문제이다

문제에서 제일 먼저 사다리만 이용한다면 최단거리로 이동하겠지 생각했지만 뱀과 사다리 조건에 따라 뱀을 타고도 더 빠르게 이동하는 경우가 있기 때문에 뱀도 무시하면 안된다

또한 방문처리를 어떻게 처리할 것인가도 생각해 봐야한다 또한 사다리나 뱀을 계속 타고 이동 해야한다는 것도 문제를 풀고 나서 결과를 뜯어서 확인해보면 내가 생각한 방법과 다르게 처리 되는 경우도 있다

 

from collections import deque
import sys
input = sys.stdin.readline

#사다리와 뱀을 이용하면 무조건 이동 조건에 방문했던 곳인지 확인은 필요x 왜냐하면 방문표시를 체크하는 조건을 단다면
#한번 방문했으면 다음번 방문할때 그냥 사다리 조건 자체를 통과하고 +주사위눈이 될 수 있기 때문이다

visted = [0 for _ in range(101)] #방문을 표시하기위함
ladder_snake =[] #사다리와 뱀을 입력 받는 리스트
board = [0 for _ in range(101)] #해당 좌표에서 주사위 굴린 수
q = deque() #bfs를 위한 큐

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

for _ in range(n+m): # 사다리와 뱀 좌표를 입력받음
    ladder_snake.append(list(map(int,input().split())))

move = [1,2,3,4,5,6]#이동 주사위
q.append(1)# 시작위치
visted[1] = 1

while q:
    a = q.popleft()

    if a == 100:
            print(board[100])
            break
    

    for i in move:
        x = a + i #현재 위치에서 이동할 수 있는 경우의 수

        if 1<=x<=100 and visted[x] == 0:

            board[x] = board[a] + 1
            q.append(x)
            visted[x] = 1

            for j in ladder_snake: #사다리 뱀 타고 이동 문제점 이전에 값이 있든 말든 새로운 값을 넣어서 다음 이점에서 시작할때 결과 오류
                if j[0] == x:
                    q.pop()#사다리나 뱀에 해당하면 일단 이전에 추가했던 것을 빼야한다
                    if visted[j[1]] == 0:
                        q.append(j[1])
                        board[j[1]] = board[a] + 1
                        visted[j[1]] = 1
                        break

많이 헤맸던 문제로 문제에서 제시한 예시말고 핵심 예시 2개를 이용해서 풀었다

반례1
1 1
13 99
8 7

답3

반례2
1 5
2 92
94 3
95 4
96 5
97 6
98 7

답 4

 

---

백준 질문