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

0. 문제 링크

 

 

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

16928번: 뱀과 사다리 게임

---

1. 풀이 방법

 

 

맨 처음에는 리스트를 인덱스에 해당하는 값으로 초기화한다.

이후 뱀 혹은 사다리의 목적지에 해당하는 곳에는 목적지의 좌표로 값을 넣는다.

그리고 deque에 첫 번째 칸과 횟수(0)를 복소수로 만들어서 넣고 시작한다.

1.  deque에서 값을 뺀다.
2. 1~6까지 주사위를 굴려본다.
3. 만약 주사위를 굴린 다음 위치가 100보다 작고, 방문하지 않았다면, 다음 위치에 해당하는 리스트의 값과 횟수를 복소수로 만들어 deque에 넣는다. 이렇게 위치에 해당하는 리스트의 값을 넣는 이유는 뱀과 사다리의 목적지로 넣기 위함이다.
4. 그리고 방문 표시를 한다.
5. 만약 주사위를 굴린 다음 위치가 100이라면 이는 최저 횟수가 보장되므로 그대로 출력한다.

---

2. 코드

 

 

from collections import deque

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

board = [i for i in range(0, 101)]

for _ in range(n + m):
    i, j = map(int, input().split())
    board[i] = j        # 뱀 혹은 사다리의 목적지로 변경함

dq = deque([1 + 0j])
dq_real_list = set()
while dq:
    cur = dq.popleft()
    for i in range(1, 7):       # 주사위
        r = int((cur + i).real)     # 주사위를 굴려 cur + i 칸에 도착함
        if r == 100:        # 만약 100에 도착했다면
            print(int(cur.imag + 1))        # 횟수를 출력함
            exit(0)
        elif r < 100:       # 100보다 작다면
            if r not in dq_real_list:       # 그리고 방문하지 않았다면 (!)
                dq.append(complex(board[r], cur.imag + 1))      # r번째에 해당하는 보드의 값을 추가함
                dq_real_list.add(r)

---

3. 마무리

 

 

크게 어렵지는 않았다.

다만, 중복으로 방문하는 부분을 잘 체크해야 할 것 같다.