[백준][C++] 16928번: 뱀과 사다리 게임 <222>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

16928번: 뱀과 사다리 게임

생각의 흐름

음 일단 횟수의 최소값을 구해야 하니, BFS 방식을 가장 먼저 떠올렸다.

 

input을 nextNumber[101]이라는 배열로 받아야 겠다 생각했다.

nextNumber[31] = 42 는 31번 칸에 도착시 42번 칸으로 사다리를 타고 올라간다 라는 의미이며,

nextNumber[30] = 25 는 30번 칸에 도착시 25번 칸으로 뱀을 타고 내려가야 한다.

 

이를 활용하여 매 칸마다 도착시, next = nowPosition + (1 ~ 6) 까지 가능한 주사위 숫자를 더해주고

next 위치에 사다리나, 뱀이 있다면 위치를 이동시켜 준다.

next 위치를 이전에 방문한적이 없다면, 방문처리하고 Queue에 삽입시켜 준다.

 

이를 Queue가 비어질때까지 반복한다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 101

int N, M;
int nextNumber[MAX];
int counter[MAX];
bool visited[MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    int from, to;
    for(int i = 0; i < N; i++) {
        cin >> from >> to;
        nextNumber[from] = to;
    }
    for(int i = 0; i < M; i++) {
        cin >> from >> to;
        nextNumber[from] = to;
    }

    queue<int> Q;
    visited[1] = true;
    Q.push(1);

    while(!Q.empty()) {
        int now = Q.front();
        Q.pop();

        for(int i = 1; i <= 6; i++) {
            int nx = now + i;

            if(nextNumber[nx] != 0) {
                nx = nextNumber[nx];
            }

            if(nx > 100) continue;

            if(!visited[nx]) {
                counter[nx] = counter[now] + 1;
                visited[nx] = true;
                Q.push(nx);
            }
        }
    }

    cout << counter[100];

    return 0;
}