문제 요약
작은 수 → 큰 수로 올라가는 사다리와 큰 수 → 작은 수로 내려오는 뱀으로 이뤄진 1~100의 보드에서 100번 칸까지 도달하기 위해 최소 몇 번의 주사위를 굴려야 할까
이 때 주사위 수는 임의로 정할 수 있다.
< 예시 >
[ 입력 ]
3 7 // 사다리의 수, 뱀의 수
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17[ 출력 ]
3
[ 힌트 ]
5를 굴려 6으로 이동한다.
6을 굴려 12로 이동한다. 이 곳은 98로 이동하는 사다리가 있기 때문에, 98로 이동한다.
2를 굴려 100으로 이동한다.< 제약 조건 >
- 1번과 100번 칸에는 사다리 및 뱀이 위치해 있지 않다.
- 모든 칸은 최대 하나의 사다리 또는 뱀을 갖음과 동시에 두 가지 모두가 한 칸에 위치한 경우는 없다.
- 마지막 주사위 굴림의 결과가 100을 넘어선 안 된다.
< 백준 >
- 골드 5 / BFS
- 출처 : https://www.acmicpc.net/problem/16928
풀이
< 설정 >
(1) 0으로 이뤄진 10 * 10 보드를 준비한다.
(2) 입력으로 주어진 사다리와 뱀의 값으로 보드를 채운다.
예를 들어, 사다리로 16 20이 들어온다면, 이는 16번째 칸을 통해 20번째 칸으로 이동할 수 있음을 의미하기에 16번째 칸에 값을 0이 아닌 20으로 채운다.
반대로, 뱀의 값으로 30 5가 들어온다면, 이는 30번째 칸을 통해 5번째 칸으로 내려감을 의미하기에 30번째 칸을 0이 아닌 5로 채운다.
(3) 주사위 굴림 횟수를 입력할 101 크기의 배열을 초기화한다.
<실행>
(1) 첫 번째 칸은 시작 위치임으로 주사위 횟수 배열에 0으로 초기화하고, 현재 위치를 큐에 삽입한다.
(2) 더 이상 이동할 칸이 없을 때까지 반복문을 동작시킨다.
(3) 주사위 값이 6인 경우가 주사위를 최소한으로 쓰는 경우임으로, 6~1 형태의 반복문을 연다.
※ 단, 현재 위치와 주사위 결과값을 더했을 때 100을 넘어선 안 된다.
(4) 다음 위치 결과값이 방문한 적 없고, 사다리 및 뱀이 없는 칸일 경우, 그대로 이동을 진행한다.
※ 큐에 다음 칸의 값을 삽입한다.
※ 그 칸까지 도달하기 위해 굴린 주사위의 횟수를 현재 칸까지 도달하기 위해 굴린 횟수 + 1로 배열에 초기화한다.
(5) 방문한 적은 없지만, 사다리 혹은 뱀이 있을 경우,
사다리 혹은 뱀의 도착 지점 칸이 방문한 이력이 있는지 검사한다.
만약 없을 경우, 위의 방식과 마찬가지로 이동을 진행시킨다.
- 최종 주사위 횟수 배열엔 해당 칸에 도달하기 위해 사용된 주사위의 횟수가 저장된다.
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BaekJoon16928 {
private static int[] board;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
board = new int[101];
for (int i = 0; i < N + M; i++) {
st = new StringTokenizer(bf.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
board[a] = b;
}
bfs();
}
private static void bfs() {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
int[] check = new int[101];
check[1] = 0;
// 횟수
while (!queue.isEmpty()) {
int cur = queue.poll();
for(int i=6;i>=1;i--) {
int next = cur + i;
if (next > 100)
continue;
if (check[next]==0 && board[next]==0) {
queue.add(next);
check[next] = check[cur] + 1;
}
// 방문한 적이 없고, 사다리 및 뱀이 없는 칸일 경우
else if (board[next] != 0) {
int move = board[next];
if (check[move] == 0) {
queue.add(move);
check[move] = check[cur] + 1;
}
}
// 방문한 적 없고, 사다리 혹은 뱀이 있는 칸일 경우
}
}
System.out.println(check[100]);
}
}
