[백준] 10830: 뱀과 사다리 게임 (C++)

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

스크래핑 문제로 open graph tag가 안뜸.

문제

---

https://ko.wikipedia.org/wiki/%EB%B1%80%EA%B3%BC_%EC%82%AC%EB%8B%A4%EB%A6%AC

글보단 그림으로 보면 편할 것이다.

 

1~100까지의 인덱스를 가진 Grid가 있지만 1차원인 배열로 봐도 상관없다.

 

뱀을 만나면 다시 내려가야 되고 사다리를 발견하면 껑충 뛰어넘어갈 수 있다.

 

 

아이디어

---

①BFS

1부터 1~6자리까지 모두 시행 후, BFS방식을 사용해 지름길을 통하거나 뱀을 피해 먼저 100에 도착하는 경우를 채택한다.

 

visit[]을 통해 방문했던 인덱스인지 확인하고 아니라면 Queue에 push한다.

 

queue에 들어간 좌표와 카운트는 level순으로 들어가고 순차적으로 빠질 수 있어 BFS가 된다.

 

Code

---

#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

int table[101];
int visit[101];

void init() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
}

void table_init(int N, int M) {
    int x, y;
    while (N--) {
        cin >> x >> y;
        table[x] = y;
    }
    while (M--) {
        cin >> x >> y;
        table[x] = y;
    }
}

void bfs(int x, int c) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, c));
    while (!q.empty()) {
        int current = q.front().first;  // 현재 좌표
        int cnt = q.front().second;     // 카운트
        q.pop();

        for (int i = 1; i <= 6; i++) {
            int next = current + i;
            if (next == 100) {
                cout << cnt + 1;  // 도착했으면 출력
                return;
            } else if (next < 100) {
                // 사다리 혹은 뱀인지 확인 
                while (table[next] != 0) next = table[next]; // 점프한 자리로 이동
                if (!visit[next]) {
                    q.push(make_pair(next, cnt + 1));
                    visit[next] = true;
                }
            }
        }
    }
}

int main() {
    init();
    int N, M;
    cin >> N >> M;
    table_init(N, M);
    bfs(1, 0);
    return 0;
}

다른 블로그를 참고하여 정리했다.