[BOJ/16928번뱀과사다리게임] c++ / BFS

문제

1번칸에서 100번칸으로 가는데 굴려야 하는 최소 주사위의 수

-뱀이 있는 칸은 y칸으로 내려감

-사다리가 있는 칸은 v칸으로 올라감

-주사위는 +1~6칸 올라갈 수 있음

 

생각

board맵에는 y, v 값을 넣어주고, vis칸에 사다리인지 뱀인지 표시하면 되겠다 생각함

 

문제풀이

1.board맵에 사다리와 뱀의 이동 칸을 저장하고, vis에 사다리는 1을 뱀은 2를 저장함

2.1번칸에서 BFS 탐색함

2-1.주사위 1~6 나올 수 있는 경우를 확인

3..만약 nx+i 가 범위를 벗어나지 않는다면

3-1.사다리 칸이라면, 큐에 푸쉬(board[nx+i], cnt+1) + 방문표시 - 올라감

3-2.뱀 칸이라면, 큐에 푸쉬(board[nx+i], cnt+1) + 방문표시 - 내려감

3-3.아무것도 없는 칸이라면 큐에 푸쉬(nx+i, cnt+1) + 방문표시 - 주사위 수만큼 올라감

4.100번째 칸에 도달하면 cnt 반환

5.cnt 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
int board[101];
int vis[101];
int N, M, u, v, x, y;
int BFS() {
    queue<pair<int, int>> Q;
    Q.push({1, 0});

    while(!Q.empty()) {
        int nx = Q.front().X;
        int cnt = Q.front().Y;
        Q.pop();
        
        if ( nx == 100 )
            return cnt;

        for ( int i = 6; i >= 1; i-- ) {
            if ( vis[nx+i] == 0 ) continue;
            if ( nx+i > 100 ) continue;

            if ( vis[nx+i] == 1 ) { // 사다리
                vis[nx+i] = 0;
                Q.push({board[nx+i], cnt+1});
            }
            else if ( vis[nx+i] == 2 ) { // 뱀
                vis[nx+i] = 0;
                Q.push({board[nx+i], cnt+1});
            }
            else {
                vis[nx+i] = 0;
                Q.push({nx+i, cnt+1});
            }
        } 
    }

    return -1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    memset(vis, -1, sizeof(vis));
    for ( int i = 0; i < N; i++ ) { // 사다리 정보
        cin >> x >> y;
        board[x] = y;
        vis[x] = 1;
    }

    for ( int i = 0; i < M; i++ ) { // 뱀 정보
        cin >> u >> v;
        board[u] = v;
        vis[u] = 2;
    }

    cout << BFS();
}