알고리즘 유형 : BFS
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/16928
소스 코드(파이썬)
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
# idx 위치에는 기본적으로 idx가 있음
# 다만 사다리나 뱀이 있는 경우는, 주사위 횟수 카운팅없이
# 끄트머리로 이동하므로, 그 끄트머리의 next_idx 값을
# idx 위치에 넣어놓아줌. 카운팅은 같으면서 동일 칸 취급
board = [i for i in range(101)]
visited = [0]*101
for _ in range(N):
x, y = map(int, input().split())
board[x] = y
for _ in range(M):
u, v = map(int, input().split())
board[u] = v
def BFS(start):
q = deque([start])
while q:
x = q.popleft()
for nx in range(x+1, x+7):
if nx > 100:
continue
# 뱀이나 사다리가 없으면 nx 그대로고, 있다면
# 그 끄트머리 번호 저장
cnt = board[nx]
if visited[cnt] == 0:
visited[cnt] = visited[x] + 1
q.append(cnt)
if cnt == 100:
return visited[100]
return False
print(BFS(1))풀이 요약
-
최단 횟수를 구하는 문제이므로 BFS를 활용한다.
인접 노드는 현재 칸의 번호에서 +1 ~ +6이다. 이를 for로 순회한다.
만약 인접 노드 nx가 100 초과라면 continue 해준다.
-
이 문제는 뱀과 사다리라는 조건이 하나 더 있다.
뱀이나 사다리의 시작 부분에 다다르면 반드시 끝 부분으로 이동해야한다.
이 때는 주사위 횟수 카운팅을 하지 않으므로, 시작칸과 끝칸을 동일시해주면 된다.
동일시해주기 위해서 약간의 로직이 필요하다.
-
보드판을 [i for i in range(101)]로 초기화해두고, 뱀과 사다리의 시작과 끝(a, b)를 입력받았을 때, board[a] = b 로 덮어씌워준다.
이 때 board[idx]의 값은 idx 위치의 칸의 정보를 의미한다.
board[idx] = idx인 경우라면 그냥 그 자체로 현재 위치임을 의미하고,
board[idx] = other인 경우라면 idx칸은 other칸과 동일시 취급된다는 의미이다.
-
for로 인접 노드를 순회할 때, 현재 실제 칸을 의미하는 cnt에 board[nx]를 넣어준다.
이렇게 하면 만약 뱀과 사다리의 경우, 인접 노드(시작 칸)를 끝 칸으로 취급하여 그 뒤의 구문을 처리하게 된다.
뒤의 구문은, 만약 인접 노드에 방문 기록이 없는 경우 visited를 1 더해주고 큐에 넣어준다.
배운 점, 어려웠던 점
-
처음에는 큐에서 뽑을 때, 그 칸이 뱀이나 사다리의 시작일 경우에 칸 변수에 뱀이나 사다리의 끝 칸 값을 덧씌워주고 visited 갱신을 해주는 식으로 작성했는데, 계속 WA가 떠서 테스트 케이스를 참고해봤다.
만약 큐에 48과 93이 있었다고 치고, 48에 99로 이어진 사다리가 있다고 가정하자. (큐에는 93이 먼저 들어와있음, 48과 93의 visited 값은 k로 같음)
그러면 일단 93이 먼저 뽑힐테고, 인접 노드 중 하나인 99에 방문을 할 것이다.
그 다음으로 48을 뽑고, board[48] == 99 이므로, visited[99] = k로 설정해줘야할테지만, 이미 앞서 93에서 99을 방문하여 k+1로 갱신해줘버렸으므로 불가능하다.
이러한 경우에 의해, 큐에서 뽑을 때 처리를 하는게 아닌, 큐에 넣을 때 뱀/사다리를 처리해줘야한다는 것을 깨달았다.
