문제 출처 : https://www.acmicpc.net/problem/16928
난이도 : 골드 5
문제 파악
이렇게 생긴 것이 뱀과 사다리 게임이라고 한다. 출처
1번 칸에서 시작해서 100번 칸에 도착해야 한다.
한 번에 할 수 있는 행동은 주사위를 1~6 굴려서 앞으로 이동하는 것.
단, 특정 칸에는 사다리 / 뱀이 있어서
그 칸에 도착하면 즉시 다른 칸으로 이동한다.
목표: 100번 칸에 도달하기 위한 최소 주사위 횟수.
왜 BFS인가?
이 문제는 그래프로 보면 아주 깔끔해진다.
- 정점: 칸 1 ~ 100
- 간선: x에서 주사위를 굴려 x+1 ~ x+6으로 가는 이동
- 간선 비용: 전부 1 (주사위 한 번 굴림 = 비용 1)
즉, 모든 간선 비용이 동일한 최단거리 문제다.
이럴 때 정답은 항상 BFS.
핵심 아이디어 move 테이블
처음엔 “각 칸에서 [1,2,3,4,5,6]으로 갈 수 있네?” 라고 보일 수 있다.
하지만 그건 어디서나 똑같아서 굳이 저장할 정보가 아니다.
이 문제에서 진짜 중요한 건 이거다:
“어떤 칸에 도착했을 때, 사다리/뱀이 있으면 어디로 강제 이동하는가?”
그래서 move 배열을 만든다.
- 기본:
move[i] = i(그 칸에 도착하면 그대로) - 사다리/뱀 입력:
a -> b면move[a] = b
해답 및 풀이 (BFS)
import sys
from collections import deque
input = sys.stdin.readline
# N = 사다리 수, M = 뱀 수
N, M = map(int, input().split())
# move[i] = i에 도착했을 때 실제로 서게 되는 칸
move = list(range(101)) # 0은 안 쓰고 1~100만 사용
for _ in range(N + M):
a, b = map(int, input().split())
move[a] = b
# dist[i] = i번 칸까지 도달하는 최소 주사위 횟수
dist = [-1] * 101
dist[1] = 0
q = deque([1])
while q:
x = q.popleft()
# 이미 100에 도달했으면 BFS 특성상 최소값이 확정이라 바로 종료 가능
if x == 100:
break
for d in range(1, 7):
nx = x + d
if nx > 100:
continue
nx = move[nx] # 사다리/뱀 처리 (없으면 그대로)
if dist[nx] == -1: # 아직 방문 안 했으면
dist[nx] = dist[x] + 1 # 주사위 1번 추가
q.append(nx)
print(dist[100])사다리/뱀은 “도착하자마자 즉시 이동”이다.
그래서 BFS에서 x+d 계산한 직후에 move[nx]를 적용해야 한다.
visited 대신 dist = -1로 방문 여부를 같이 처리하면 깔끔하다.
nx > 100은 갈 수 없으니 반드시 스킵.
다음날 다시 풀어본 코드
import sys
input = sys.stdin.readline
from collections import deque
# 사다리의 수 N, 뱀의 수 M
N,M = map(int,input().split())
# 사다리, 뱀 결국 a -> b 워프 시켜주는 통로 같은 개념 같이 저장
# portal[1] = 1, portal[6] = 6 원래 이런데 portal[6] = 뱀의 번호 이런식으로 해놓으면 portal[6]이 워프됨
portal = [ i for i in range(101) ]
# 포탈 연결
for _ in range(N+M):
blackhole, whitehole = map(int,input().split())
portal[blackhole] = whitehole
# 1 부터 100까지 가는데 몇번의 최소 횟수 인지 구해야 함
visited = [-1 for _ in range(101)] # 방문 여부 겸 횟수 카운팅용도
def bfs(start):
q = deque()
q.append(start)
visited[start] = 0
while q:
X = q.popleft()
# 100에 도착했다면 횟수 리턴
if X == 100:
return visited[X]
for i in range(1,7):
nx = X + i
if nx > 100:
continue
if visited[portal[nx]] == -1: # 방문하지 않았다면
visited[portal[nx]] = visited[X] + 1
q.append(portal[nx])
print(bfs(1))주사위를 굴리고 포탈(뱀,사다리) 를 타야하는데 그전에 포탈처리를 하여 잘못된 코드를 짰었다. 내일 다시 풀어보겠다.
다다음날 다시 푼 코드
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int,input().split())
portal = [i for i in range(101)]
count = [-1 for _ in range(101)]
for _ in range(N + M):
blackhole, whitehole = map(int,input().split())
portal[blackhole] = whitehole
queue = deque()
queue.append(1)
count[1] = 0
while queue:
X = queue.popleft()
if X == 100:
print(count[100])
sys.exit(0)
for d in range(1,7):
nx = X + d
if nx > 100:
continue
elif count[portal[nx]] == -1:
queue.append(portal[nx])
count[portal[nx]] = count[X] + 1다다다음날 다시 푼 코드
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int,input().split())
portal = [i for i in range(101)]
for _ in range(N + M):
a, b = map(int,input().split())
portal[a] = b
count = [-1 for _ in range(101)]
queue = deque()
queue.append(1)
count[1] = 0
while queue:
x = queue.popleft()
for d in range(1,7):
nx = x + d
if nx > 100:
continue
else:
after_warp = portal[nx]
if count[after_warp] == -1:
count[after_warp] = count[x] + 1
queue.append(after_warp)
print(count[100])이번엔 한번에 풀었다.
Frontend Engineers