1. 문제
-
뱀과 사다리 게임 ⇒ 도착점에 도착할 수 있는 최소 횟수?
-
게임판 10 x 10, 1 ~100까지 수 순서대로 적혀있음
- ex) i번 칸 ⇒ 주사위 4 나옴 ⇒ i+4칸
-
1번 ⇒ 100번 칸으로 이동
- 주사위 굴린 결과가 100 넘어가면 이동 불가
- 도착한 칸이 사다리면 사다리 타고 위로 (원래 있던 칸보다 크게)
- 도착한 칸이 뱀이라면 뱀 타고 아래로 (원래 있던 칸보다 적게)
-
1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아님
-
모든 칸은 최대 하나의 사다리 또는 뱀 → 동시에 두 가지를 모두 가지고 있는 경우는 없다.
-
항상 100번 칸에 도착할 수 있는 입력만 주어진다.
⇒ 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값?
-
입력 :
| 사다리의 수 **N** 뱀의 수 **M** (1 ≤ N ≤ 15, 1 ≤ M ≤ 15)
| N개 줄 : 사다리의 정보 x, y (x < y) (x번 칸에 도착하면 y번 칸으로 이동)
| M개 줄 : 뱀의 정보 u, y (u > v) (u번 칸에 도착하면 v번 칸으로 이동) -
출력 :
100번 칸에 도착하기 위해 주사위를 굴려야 하는 최소 회수 -
예제 입력
2. 풀이
- BFS
- 현재 위치 cur과 주사위를 돌린 횟수 rolls를 queue 에 담아서 이용하며, queue에서 원소를 하나씩 빼서 목적지 100인지 확인하거나 주사위를 굴린다
- 만약 현재 위치가 목적지 100이라면 여태 주사위를 굴린 횟수 rolls를 출력하고 while문 탈출한다.
- 아직 목적지에 도달하지 않아, 주사위를 굴린다면 1~6 사이의 숫자를 현재 위치에 더해서,
- 다음 위치가 100 이하의 숫자라면
- 해당 위치가 사다리에 해당된다면 or 뱀에 해당된다면 다음 위치를 다시 갱신
- 방문하지 않은 위치라면 주사위를 1번 굴렸으므로, queue에 해당 위치와 굴린횟수+1을 추가하고, 방문 처리
3. 코드
import sys
from collections import deque
def solution():
input = sys.stdin.readline
N, M = map(int, input().split())
ladders = dict()
snakes = dict()
for _ in range(N):
x, y = map(int, input().split())
ladders[x] = y
for _ in range(M):
u, v = map(int, input().split())
snakes[u] = v
visited = [False] * 101
rolls = 0
#BFS
cur = 1
queue = deque()
queue.append((cur, rolls))
visited[1] = True
while queue:
cur, rolls = queue.popleft()
if cur == 100:
print(rolls)
break
for dice in range(1,7):
next = cur + dice
if next <= 100:
if next in ladders.keys():
next = ladders[next]
elif next in snakes.keys():
next = snakes[next]
if not visited[next] :
queue.append((next, rolls+1))
visited[next] = True
solution()+α
- 1차 시도
- 문제에 나온 대로 10*10 board를 만들고 번호에 따라 i행 j열을 계산하고,,, 문제를 너무 복잡하게 생각해서 삽질을 많이 함…
- 사다리를 타고 이동한 위치가 뱀의 시작 위치일 수도 있다고 문제를 해석해서 ( 단순히 시작 위치만 겹치지 않는 것으로 해석해서) 주사위를 굴린 후 말의 위치를 계산해내는 것만으로도 별도의 함수를 제작해야한다고 생각했다…^__^
BFS/DFS 문제 오랜만에 풀었더니 감 다까먹었다.. 열공하자,,
