https://www.acmicpc.net/problem/16928
내 알고리즘
우선 이걸 기본 생각으로 깔고 간다.
그리고
이런 식으로 사다리, 뱀은 주사위를 굴리는게 아니므로 먼저 처리해줄 필요가 있다.
더 많은 주사위를 굴리는게 먼저 마지막칸에 도달하여 그 횟수가 쓰여지면 답이 틀리게 되기 때문이다.
사다리, 뱀으로 간 칸은 큐의 맨앞에 넣어 먼저 처리하게 만들면
이렇게 올바른 답이 나오게 된다.
즉, 현재 그 칸에 가는 최소 횟수를 배열에 저장 -> 갱신이 되면 이를 큐에 넣음
(왜냐하면 이전에 큐에 들어간 적이 있다고 해도 갱신이 되면 그 칸에서 가는 경우를 다시 갱신해야 하므로)
이를 반복하여
import sys
from collections import deque
input = sys.stdin.readline
def BFS(arr, queue, cur, ladder, snake):
if ladder[cur]:
if arr[cur] < arr[ladder[cur]]:
queue.appendleft(ladder[cur])
arr[ladder[cur]] = arr[cur]
return
if snake[cur]:
if arr[cur] < arr[snake[cur]]:
queue.appendleft(snake[cur])
arr[snake[cur]] = arr[cur]
return
for i in range(1, 7):
if arr[cur] + 1 < arr[cur + i]:
queue.append(cur + i)
arr[cur + i] = arr[cur] + 1
return
N, M = map(int, input().split())
steps = [10000] * 107
ladder = [0] * 101
snake = [0] * 101
for i in range(N):
x,y = (map(int, input().split()))
ladder[x] = y
for i in range(M):
x,y = (map(int, input().split()))
snake[x] = y
queue = deque([1])
steps[1] = 0
while steps[100] == 10000:
BFS(steps, queue, queue.popleft(), ladder, snake)
print(steps[100])
이러한 코드가 나오게 된다.
먼저 방문한 노드를 다시 방문하지 않는 방법도 고민해보았으나 그 방법은 안된다.
이런 식으로 갱신되는 경우가 분명 존재하기 때문이다.
다른 사람의 코드
rkaxhdals의 코드
나는 아무리 파이썬을 갓 배웠다지만 코드가 900바이트가 넘는데
딱히 숏코딩을 한 것도 아닌데도 코드가 366바이트로 세배 가까이 차이난다는게 감탄스럽다.
이러한 코드들을 많이 읽어보며 파이썬스럽게 짜는 연습을 해볼까 한다.
구현을 간단하게 할 수 있으면 어디서 잘못되었는지 알기 용이할 거 같고
또 실수가 있어도 찾기 쉬울 것이기 때문이다.
알고리즘을 풀기 위해 파이썬을 공부한 이유이기도 하다.
q = [(1, 0)]
arr = list(range(106)) # 99에서 주사위가 던져지면 최대 105이므로 배열을 106칸 선언한 듯하다.
dice = tuple(range(1, 7)) # iterator range를 튜플로
# 즉 dice = (1,2,3,4,5,6)이 된다.
visited = [False] * 106
visited[1] = True
# 처음에 1번째부터 방문할 것이기 때문에 visited[1]을 미리 True로 설정
# 파이썬에서 안 쓰는 변수에 대한 관례 '_'
for _ in range(sum(map(int, input().split()))):
# 사다리의 개수와 뱀의 마릿수가 N과 M으로 각각 들어오는데 sum을 통해 이를 한번에 처리
a, b = map(int, input().split())
arr[a] = b
# 배열에 이를 넣어 O(1)로 탐색할 수 있게 만듬
for x, c in q:
if x == 100: print(c); break
if x > 100: continue # 이건 불필요한듯 하다, 어차피 갱신에 쓰이지도 않고 마지막 100번째 칸에 도달하기 위해서는 주사위를 굴려야 하는데 그럼 100이 먼저 q에서 나올 것이기 때문
for n in dice: # n = 1,2,3,4,5,6
if not visited[x + n]:
q.append((arr[x + n], c + 1))
# q에 있는 튜플 (x,y)의 의미는 x번째 칸에 도달하는 현재 계산한 최소 스텝의 횟수가 y라는 의미
# arr[x]는 x에 뱀이나 사다리가 연결되어 있지 않으면 자기 자신을 가리킨다.
visited[x + n] = True
이 알고리즘이 어떻게 동작하는지 한번 보자.
요지는 한번에 한 스텝이다.
이런 식으로 n step을 가는 경우는 한번에 찾으므로 100에 처음 도달했을 때가 100에 도달하는 최소 스텝임이 명백하다.
이는 사다리는 한 칸에 한개라는 명백한 가정이 있으므로 작동한다.
