코딩테스트/문제

[백준] 16928번 뱀과 사다리 게임

스키(ski) 2022. 9. 4. 19:01
문제 내용

https://www.acmicpc.net/problem/16928

 

16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net

해결 코드
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
#include <iostream>
#include <queue>
 
using namespace std;
 
int ladder_snake[101]; //뱀과 사다리 저장
bool visited[101];
queue<int> q;
 
void Push(int n) {
    if (!visited[n]) {
        q.push(n);
        visited[n] = true;
    }
}
 
int BFS() {
    Push(1);
    int cnt = 0; //주사위 굴린 횟수
 
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int a = q.front();
            q.pop();
 
            if (a == 100)
                return cnt;
 
            for (int j = 1; j <= 6; j++) {
                int idx = a + j;
                if (idx <= 100) {
                    if (ladder_snake[idx]) {
                        Push(ladder_snake[idx]);
                        visited[idx] = true;
                    } else {
                        Push(idx);
                    }
                }
            }
        }
        cnt++;
    }
}
 
int main() {
    int n, m;
 
    cin >> n >> m;
 
    for (int i = 0; i < n + m; i++) {
        int a, b;
        cin >> a >> b;
 
        ladder_snake[a] = b;
    }
 
    cout << BFS();
}
 
 cs

 

주요 개념 
  • 그래프 탐색: 너비 우선 탐색(Breadth-First Search,BFS)

 

주의 사항
  1. 문제를 보면 DP를 사용할것 같은 문제인데, 해당 문제는 단방향으로 향하는 문제가 아니기에 DP를 사용하면 안된다.
  2. [모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다.]라는 조건에 유의해서 풀어야한다.