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

백준 16928 - 문제

백준 16928 - 입/출력

---

풀이

뱀과 사다리 게임은 쉽게 출발지에서 주사위를 굴려 도착지까지 도달해야 하는 게임이다.

무조건 큰 숫자로 이동하는 '사다리'와 작은 숫자로 이동하는 '뱀' 이지만,'사다리-사다리' 보다 '뱀-사다리'가 더 빠를 수 있다는 점에 유의하자.

즉, 절대적으로 좋고(사다리) 안 좋은(뱀) 조건이 없다. 필자는 개인적으로 뱀을 좋아한다 (~쉬익~쉭)

그 때문에 이동 가능한 모든 칸에 대해서 탐색을 진행해야 한다.

 

다음 조건을 유의하자

• 주사위를 굴려 나온 수만큼 이동한 칸에 '사다리' 또는 '뱀'이 있을 때, 선택이 아닌 강제로 이동을 해야한다.
• '사다리'와 '뱀' 을 동시에 가지는 경우는 없다.
• 게임은 1회 이상 진행된다.

'N + M <= 30' 이므로 전체 graph 대비 점유율이 낮아, dictionary를 사용해 풀이했다.

사다리와 뱀은 중복되지 않으니 한 번에 입력받아 주자.

visited 배열을 사용해 중복 탐색을 방지함과 동시에 해당 칸까지 방문하기 위한 횟수를 기록했다.

기본적으로 주사위를 마음대로 던질 수 있다는 조건이 있지만, '사다리'와 '뱀'라는 변수가 있으므로 항상 큰 주사위 숫자를 기준으로 탐색하는 방식은 최소 횟수임이 성립하지 않는다.

즉, 주사위를 굴려 나올 수 있는 모든 수에 대해 탐색을 시도해야 한다.

'사다리'나 '뱀'이 있으면 이동한 후의 숫자( jump[next_num] )를 다음 탐색 대상( next_num )으로,

아무것도 없는 경우에는 주사위로만 이동한 칸의 숫자( next_num )을 queue에 넣어주면 된다.

---

소스코드

소스코드 보기

---

출처

16928번: 뱀과 사다리 게임