16928

날짜 : 2023. 07. 13

사용 언어 : python

 

문제

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

 

 

코드

import sys
from collections import deque


def game(start):
    res = int(1e9)
    queue = deque()
    queue.append([start, 0])
    while queue:
        now, cnt = queue.popleft()  # 현재 위치, 주사위 굴린 횟수
        # print(now, cnt)
        if now == 100:  # 결승점 도달
            print(cnt)
            return
        if len(graph[now]) > 6:
            visited[graph[now][-1]] = True
            queue.appendleft([graph[now][-1], cnt])
            continue
        for i in graph[now]:
            if i <= 100 and not visited[i]:  # 범위 포함
                visited[i] = True  # 방문처리
                queue.append([i, cnt + 1])  # 일반

n, m = map(int, sys.stdin.readline().split())  # 사다리 수, 뱀의 수
graph = [[i+1, i+2, i+3, i+4, i+5, i+6] for i in range(101)]
visited = [False] * 101
# 사다리
for i in range(n):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
# 뱀
for i in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)

game(1)

 

 

풀이

- 주사위를 굴려서 하나의 지점 node에서 갈 수 있는 케이스는 node + 1 ~ node + 6이다.

- 다만, 사다리로 연결되어 있는 경우 주사위를 굴리지 않고 갈 수 있기 때문에 주사위 굴린 횟수를 가산하지 않고, 이동했을 때에는 횟수가 전부 동일하기 때문에 큐에서 가장 앞선에 push하고, 곧바로 continue해서 불필요한 가산을 막는다.

- 그 다음 100에 도착한 경우 값을 출력한 다음 리턴한다.

 

 

알게된 점

- 반례를 확인해보니 디버깅을 하면서 큐에서 카운트가 가장 적은 경우 맨 뒤에 있으면 100에 도달해도 그 수가 min 값이 되지 않는 경우를 발견했다.

- 그래서 사다리로 이동했을 경우 방문처리와 함께 appendleft를 사용해서 큐에서 가장 우선적으로 체크하도록 변경했고, continue를 사용해 불필요한 이동을 막았다.

- 되게 자잘자잘한 고려사항이 있어서 많이 오답을 낸 것 같다 :(

 

 

참고 사이트

-