💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 1228KB Time 0ms Code Length 716B
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
#include <stdio.h>
#include <queue>
using namespace std;
int n, m;
int cnt = 0;
int move_map[101];
int visited[101];
int main() {
scanf("%d %d", &n, &m);
// 이동하는 구간 저장
for (int i = 0; i < n + m; i++) {
int x, y;
scanf("%d %d", &x, &y);
move_map[x] = y;
}
queue<int> q;
q.push(1);
int result = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == 100) {
result = visited[now];
break;
}
for (int i = 1; i <= 6; i++) {
int next = now + i;
while (move_map[next] != 0) {
next = move_map[next];
}
if (next > 100) continue;
if (visited[next] != 0) continue;
visited[next] = visited[now] + 1;
q.push(next);
}
}
printf("%d", result);
}
이 코드는 뱀과 사다리 게임을 구현한 것이다.
- 먼저 n과 m을 입력받아서 이동하는 구간을 저장한다.
- 그 후, 1부터 100까지의 숫자를 방문하는데, 각 숫자에서 1부터 6까지의 주사위 눈금을 더해가며 이동한다.
- 만약 이동 중에 뱀이나 사다리가 있다면 해당 위치로 이동한다.
- 이동한 위치가 100이 되면 결과를 출력하고 종료한다.
