골드 V

💡문제 분석 요약

BFS

💡알고리즘 설계

움직이는 것은 그 전에 영향을 받으므로, 이전 값의 영향을 넣을 수 있는 bfs를 떠올렸으며, 여러 경우의 수를 따져가면서도 최소를 카운팅 해야하기에 dfs가 아닌 bfs로 풀었다.

기본적으로 index =1에 1, 2에는 2값을 가지는 보드를 생성한 후, 뱀과 사다리로 연결되어 움직이는 경우에는, 도착지의 값을 입력한다.

4→62일 경우, board[4]=62

visited에는 방문한 번호의 인덱스를 가진 칸에 True를 넣는다.

그리고 queue에 돌아가면서 1~6까지 더한 뒤, 범위 내라면 queue에 추가한다.

💡코드

import sys
from collections import deque 
input= sys.stdin.readline
n,m = map(int,input().strip().split(' '))
board = [i for i in range(101)]
visited = [False for _ in range(101)]

for _ in range(n):
    x,y = map(int,input().strip().split(' '))
    board[x] =y
    
for _ in range(m):
    u,v = map(int,input().strip().split(' '))
    board[u] =v
    
q= deque()

q.append((1,0))
visited[1] = True

while q:
    new = deque()
    n,cnt =q.popleft()
    if n==100:
        print(cnt)
        break
    for i in range(1,7):
        move = n+i
        if 0<move<=100 and not visited[board[move]] and 0<board[move]<=100 :
            q.append((board[move],cnt+1))
            visited[board[move]] = True

💡오류 난 이유

range오류. visited와 board의 range가 달랐고 1~101까지로 설정한게 잘못이었다. 인덱스와 그에 대한 값을 무엇으로 설정할건지 확실하게 하자.
counting을 위해 new_queue를 생성하고, 그에 따른 값을 q에 다시 넣어서 초기화했지만, 이러면 1~6까지의 경우의 수를 다 넣지 않고 초기화 되므로 더 오래걸린다. 따라서 q 자체에 단계인 cnt를 넣는 것으로 변경하였다.

💡 기억할 것

인덱스와 그에 대한 값을 무엇으로 설정할건지 확실하게 하자.
활용하려는 코드를 적용했을 때 어떤 값이 실제로 들어가는지 그려보고 적용해보자.