안녕하세요,
재재입니다.
BOJ 16930 달리기 문제 풀이입니다.
BOJ 16930 달리기
(1) 문제 설명
분류 : graph, bfs
출처 : https://www.acmicpc.net/problem/16930
(1,000 이하) N 과 M 이 주어지며,
K 가 주어집니다. 한방향으로 한번에 최대 K칸 이동 할 수 있으며,
최소한의 시간으로 도착지점에 도착하면 됩니다.
(2) 풀이 도출
문제를 읽다보면,
자연스럽게 bfs 로 접근하게 되는 문제입니다.
다만, K 칸을 이동 할 수 있다는 점이 가장 신경쓰이는데요.
K칸을 직접 가지 않고 해결 할 수 있는 방법이 있는가? 를 고민해보면 힌트가 될 수 있습니다.
queue 를 사용하면, 각 칸에 도달하는 시간은 항상 가장 짧다는 것을 보장 할 수 있는데요,
단순히 bfs 를 돌리면 시간초과에 직면하게 됩니다.
우선순위 큐를 사용하지 않고 해결 할 수 있다는 생각을 먼저 하게되면,
K 칸을 탐색하는데 효과적인 방법이 필요함을 생각 할 수 있습니다.
한방향으로 직진을 하다가 언제 멈추는 지 생각해보면,
아래와 같이 나열 할 수 있습니다.
- 직진하다가 벽을 만나는 경우
- 더이상 진행할 수 없는 경우
- 방문할 칸이 이미 전에 방문이 된 경우
여기서 핵심 힌트는 바로 3번째 입니다.
(3) 정답 코드
BOJ 16930 달리기