문제
1×1 ~ 10×10 크기의 보드(1번100번 칸)에서 시작 칸(1번)에서 목표 칸(100번)까지 이동하는 최소 주사위 횟수를 구하는 문제이다. 사다리와 뱀이 있어 특정 칸에 도달하면 다른 칸으로 이동한다. 주사위 눈은 16이다.
입력
- 첫째 줄: 사다리 수 N, 뱀 수 M
- 다음 N줄: 사다리 시작 칸, 도착 칸
- 다음 M줄: 뱀 머리 칸, 꼬리 칸
출력
- 1번 칸에서 100번 칸으로 이동하기 위한 최소 주사위 횟수
예제
| 입력 | 출력 |
|---|---|
3 7 32 62 42 68 12 98 95 13 97 25 93 37 79 27 75 19 49 47 67 17 | 3 |
풀이
BFS를 이용하여 1번 칸에서 100번 칸까지의 최단 경로(최소 주사위 횟수)를 구한다. 사다리와 뱀을 이동 매핑 배열로 처리한다.
- 사다리와 뱀을
lad배열에 저장한다.lad[a] = b이면 a 칸 도달 시 b 칸으로 이동한다. - 1번 칸에서 BFS를 시작하고,
map[i]에 i 칸에 도달하기까지의 주사위 횟수를 저장한다. - 현재 칸에서 주사위 1~6을 굴려 이동할 칸 n을 계산한다.
lad[n] != 0이면 해당 칸에 사다리/뱀이 있으므로 이동 목적지로 대체한다.- 방문하지 않은 칸만 큐에 추가하여 중복 방문을 방지하고, 100번 칸에 도달하면 종료한다.
핵심 아이디어: 최소 이동 횟수이므로 BFS가 적합하다. 사다리와 뱀 모두 lad 배열로 통합 관리하면 코드가 단순해진다. 방문 체크를 사다리/뱀 도착지에도 즉시 적용하여 불필요한 탐색을 줄인다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day110BOJ16928뱀과사다리BFS { // 16928 뱀과 사다리 게임
static int N, M;
static int[] map, lad;
static boolean[] visit;
static Queue<Integer> q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[101];
lad = new int[101];
visit = new boolean[101];
for (int i = 0; i < N + M; i++) {
st = new StringTokenizer(br.readLine());
lad[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
}
q = new LinkedList<>();
q.offer(1);
map[1] = 0;
visit[1] = true;
while (!q.isEmpty()) {
int c = q.poll();
if (c == 100) break;
for (int i = 1; i < 7; i++) {
int n = c + i;
if (n > 100) continue;
if (visit[n]) continue;
visit[n] = true;
if (lad[n] != 0) {
if (!visit[lad[n]]) {
q.offer(lad[n]);
visit[lad[n]] = true;
map[lad[n]] = map[c] + 1;
}
} else {
q.offer(n);
map[n] = map[c] + 1;
}
}
}
System.out.println(map[100]);
br.close();
}
}복잡도
- 시간: O(V + E) — 칸 수 100개, 간선 수 최대 600개
- 공간: O(V) — 방문 배열 및 큐