[BOJ] 뱀과 사다리 게임

---

코드

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

# 현재좌표에서 주사위 1~6에 대해 너비우선탐색
# 방문한 좌표는 방문처리
# 뱀or사다리 정보 -> 배열

def bfs():
    q = deque()
    q.append((1, 0))    # (x, t) = (현재좌표, 현재까지 주사위를 던진횟수)
    visited[1] = True
    while q:
        x, t = q.popleft()
        if x == 100:    # 종료조건
            print(t)
            break
            
        for i in range(1,7):    # 주사위 결과 1~6에 대해
            if 1 <= x+i <= 100:
                if jumpTable[x+i] == 0 and not visited[x+i]:    # 뱀이나 사다리가 없는 경우
                    q.append((x+i, t+1))
                    visited[x+i] = True
                elif jumpTable[x+i] != 0:    # 뱀 또는 사다리가 있는 경우 해당하는 좌표로 (방문하지 않은경우) 이동
                    dest = jumpTable[x+i]
                    if not visited[dest]:
                        q.append((dest, t+1))
                        visited[dest] = True
    

jumpTable = [0]*101        # 뱀, 사다리 정보
visited = [False]*101    # 방문여부
n, m = map(int, input().split())    # 사다리, 뱀

# 뱀과 사다리 정보 입력
for _ in range(n+m):
    frm, to = map(int, input().split())
    jumpTable[frm] = to

bfs()

결과

풀이 방법

• 너비우선탐색(BFS)를 활용하는 문제이다
• 현재 좌표에서 주사위를 던졌을 때 도착할 좌표와 현재까지 주사위를 던진 횟수를 큐에 넣고 방문처리한다.
• 단, 도착할 좌표가 방문하지 않은 좌표인 경우에만 큐에 넣는다.
• 또한, 주사위를 던진 결과 뱀과 사다리가 있는 좌표인 경우 그것을 타고 도착할 좌표가 이미 방문한 좌표인지 확인해야 한다.
• 뱀 또는 사다리 정보는 배열에 저장하였다.
• 방문처리는 큐에서 꺼낸 다음이 아니라 큐에 넣고 나서 곧바로 방문처리해야 시간초과가 발생하지 않는다.

---