[BOJ] 16928: 뱀과 사다리 게임 [DFS/BFS](Python)

문제 링크

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

16928번: 뱀과 사다리 게임

소스 코드

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

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

ladder = {} # 사다리 정보
for i in range(n):
    start,end = map(int,input().rstrip().split())
    ladder[start] = end

snake = {} # 뱀 정보
for i in range(m):
    start,end = map(int,input().rstrip().split())
    snake[start] = end

answer = []
visited = [False] * (101) # 방문 여부

q = deque([])
q.append((1,0)) # 시작점,이동 횟수
visited[1] = 0 # 방문 처리 (사실 할 필요 x)

while q:
    cur,cnt = q.popleft() # 현위치,이동 횟수
    if cur == 100: # 100에 도착하면 중단
        print(cnt)
        break

    for i in range(1,7):
        next = cur + i # 주사위로 6칸 이동

        # 방문한 적 없는 칸이면
        if 1 <= next <= 100 and not visited[next]:
            visited[next] = True # 방문 처리
            if next in ladder: # 사다리 이동
                next = ladder[next]
            elif next in snake: # 뱀 이동
                next = snake[next]
            q.append((next,cnt+1)) # 큐에 추가

 

해설

• BFS를 이용한 풀이
• 방향 벡터 없이 그래프를 탐색
• '사다리', '뱀'은 반드시 이용

 

BFS, 방향 벡터 없음

생각해보면 별거 아닌 차이로 인해 한참을 씨름한 문제다.

조금 독특한 것은 방향 벡터 없이 그래프를 탐색하는 구조라는 점이다.

보통은 행과 열을 기준으로 탐색을 하도록 되어있는데 단순히 1~6을 더하면서 탐색을 수행한다.

 

'사다리', '뱀'은 반드시 이용

이 문제의 핵심 포인트는 '사다리' 혹은 '뱀'은 반드시 이용한다는 것이다. 

사다리와 뱀의 시작 좌표가 방문 처리되어있다고 해서 이 경우를 처리하지 않고 지나가면 최적의 해를 구하지 못하는 테스트 케이스가 존재하는 것 같다.(22%쯤 오답 처리)

즉, 뱀을 타고 내려 왔다가 다른 사다리를 이용해서 올라가는 것이 더 적은 횟수로 목표 지점에 도달하는 방법이 될 수 있다는 것이다.

 

따라서 현재 칸 cur 에서 1~6을 각각 더해서 구한 next 가 방문한 적이 없다면

 

1) 방문 처리를 하고(visited[next] = True)

2) 사다리 혹은 뱀을 타고 이동한 뒤(해당 사항 없는 경우는 그대로 둔다)

3) 도착점을 새로운 시작점으로 삼을 수 있도록 큐에 추가한다.(카운트 up)

 

효율 개선 아이디어

결과적으로 작은 숫자에서 큰 숫자로 이동하는 사다리나, 큰 숫자에서 작은 숫자로 이동하는 뱀 딕셔너리, 둘 다 이용해야 하므로 두 딕셔너리를 하나로 합치는 것이 좀 더 효율적이고 깔끔한 풀이를 작성하는데 도움이 되었을 것 같다.