[Java] 백준(골드-5) 16928번 - 뱀과 사다리 게임
문제 풀이
이번 문제는 너비 우선 탐색 BFS를 이용해 간단하게 풀 수 있다.
아이디어 도출
10x10 크기의 게임 보드판에서 주사위를 던져 나오는 눈의 숫자만큼 이동하면서 사다리가 나오면 넘어가고, 뱀이 나오면 돌아오면서 100번째 칸에 도달했을 때 던진 주사위 횟수를 구해야 한다.
필자는 게임 보드판을 만들 때 상,하,좌,우 탐색 이동이 없어서, 2차원 배열보다 1차원 배열을 활용하는게 쉽다고 느껴서 1치원 배열을 이용했다.
예제 1번을 토대로 아레 보드판을 만드는 과정을 알아보자.
1
2
3
4
1 2 3 4 5 6 7 8 9 10
11 12(98) 13 14 15 16 17 18 19 20
...
91 92(37) 93 94(13) 95 96 97(25) 98 99 100
인덱스가 12인 위치에 98을 삽입하는 방식으로 배열의 값을 입력받는다면, 12 위치에 도달했을 때 98 위치로 이동하도록 하면 된다.
다음으로는 주사위를 굴려 나온 횟수를 어떻게 저장할까?
BFS 탐색을 통해 주사위를 굴리면서 보드판을 탐색해야 하니, 1부터 6까지 큐에 삽입하고 방문 여부 체크를 한다.
만약, 1이 나왔다면 다음엔 2부터 7까지 이동할 수 있다. 이때, 2부터 6까지는 1번만 던져 갈 수 있도록 처리했으니(방문 여부 체크) 7에는 한 번 더 던져야 하는 횟수인 2를 기록하면 된다. 그렇게 주사위를 던져나가면서 주사위 던진 횟수를 방문 배열에 기록하는데 사다리 위치가 나올 경우 12 위치에서 98 위치로 탐색을 건너뛰기 때문에 98 위치부터는 주사위 던진 횟수를 2부터 기록하게 된다. 결국, 99, 100까지는 주사위 3번만 던지면 이동할 수 있기 때문에 3을 출력하면 된다.
설명이 좀 길었지만 문제 풀이를 위한 아이디어는 다음과 같다.
- 보드판을 1차원 배열을 활용해 1부터 100까지 채우기
- 보드에 사다리 값을 갱신한다. - 사다리[0]에는 사다리[1] 값을 삽입
- 보드에 뱀 값을 갱신한다. - 뱀[0]에는 뱀[1] 값을 갱신한다.
- 1부터 BFS 탐색을 시작한다.
- 주사위를 굴려 100번째 칸을 벗어날 경우 탐색을 스킵하고, 방문하지 않은 칸이라면 주사위 굴린 횟수를 1 증가시켜 갱신해나간다.
- BFS 탐색 종료 후, 100번째 칸에 기록한 주사위 굴린 횟수를 출력한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.io.*;
import java.util.*;
class Main {
static int[] dx = new int[]{1, 0, -1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
static int[] board;
static int[] visited;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
// 1. 보드판을 1차원 배열을 활용해 1부터 100까지 채우기
// 2. 보드에 사다리 값을 갱신한다. - 사다리[0]에는 사다리[1] 값을 삽입
// 3. 보드에 뱀 값을 갱신한다. - 뱀[0]에는 뱀[1] 값을 갱신한다.
// 4. 1부터 BFS 탐색을 시작한다.
// 5. BFS 탐색을 통해 100번째 칸에 도달할 때까지 주사위를 굴린다.
// 6. 100번째 칸을 방문하면 주사위 굴린 횟수를 출력한다.
// 보드판의 크기 1~100만큼 초기화
board = new int[101];
visited = new int[101];
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 1차원 배열인 게임 보드판을 1부터 100까지 채운다.
for(int i=1; i<=100; i++) {
board[i] = i;
}
// 사다리와 뱀의 위치를 보드판의 기록한다.
while(N --> 0) {
st = new StringTokenizer(br.readLine());
int ladder1 = Integer.parseInt(st.nextToken());
int ladder2 = Integer.parseInt(st.nextToken());
board[ladder1] = ladder2;
}
while(M --> 0) {
st = new StringTokenizer(br.readLine());
int snake1 = Integer.parseInt(st.nextToken());
int snake2 = Integer.parseInt(st.nextToken());
board[snake1] = snake2;
}
// 1부처 BFS 함수를 통해 탐색을 진행한다.
BFS(1);
// BFS 탐색 종료 후, 100번째 칸 방문시 주사위를 굴린 횟수를 출력한다.
bw.write(visited[100]+"\n");
}
}
static void BFS(int node) {
Queue<Integer> q = new LinkedList<>();
q.offer(node);
visited[node] = 0;
while(!q.isEmpty()) {
int now = q.poll();
// 100번째 칸에 도달하면 순회 종료
if(now == 100) {
return;
}
// 큐가 빌때까지 주사위를 굴려 나오는 경우를 탐색하기 (1~6)
for(int i=1; i<=6; i++) {
// 주사위 굴려서 이동할 수 있는 칸
int next = now + i;
/**
* 주사위를 굴려서 보드판의 범위를 벗어나면 안된다.
* 이때, 던진 주사위 이동을 무시한다.
*/
if(next > 100) {
continue;
}
/*
* 주사위를 굴려 이동한 보드판 위치가 방문하지 않았다면,
* 해당 위치를 큐에 삽입하여 BFS의 탐색 대상이 될 수있도록 한다.
* 또한, 방문 배열에 주사위 굴린 횟수를 갱신한다.
*/
if(visited[board[next]] == 0) {
q.offer(board[next]);
visited[board[next]] = visited[now] + 1;
}
}
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.