(C++) - 백준(BOJ) 16928번 : 뱀과 사다리 게임

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

bfs로 푼 문제였습니다.

 

풀이방법

 1. 뱀과 사다리의 {출발점, 도착점}들을 vector v에 저장합니다.

 

 2. bfs를 시행합니다. queue에는 pair<현재 위치, 주사위 던진 횟수>가 저장됩니다. 현재위치가 100일 때의 던진 횟수를 ans와 비교해 최솟값을 넣어줍니다. 1부터 시작하여 현재 위치 x에서 x+i (1<= i <= 6) 로 이동했을 때 2가지의 경우로 다음 위치를 표현해 queue에 push해줍니다. x+i의 위치가 100을 넘었거나 현재 칸을 이미 방문했을 경우 continue, 아닌 경우엔 현재 칸을 방문했음을 표시, v[nx]에 뱀 또는 사다리가 설치되어 있다면 이동한 위치는 v[nx][0]이므로 queue에 {x+i, 던진횟수 + 1} 이 push 됩니다. 설치되어 있지 않다면 주사위 를 던진 후 있게되는 {위치 x+i, 던진횟수 + 1}을 push하게 됩니다.

 

 3. ans를 반환합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m;
vector <int> v[101];
int bfs(){
    int visited[101];
    memset(visited,0,sizeof(visited));
    int ans = 0x3f3f3f3f;
    queue <pii> q;
    q.push({1,0}); //현재 위치, 주사위 던진 횟수
    
    visited[1] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int moved = q.front().second;
        if(x == 100) {ans = min(ans, moved); break;}
        q.pop();
        for(int i = 1; i <= 6; i++){
            int nx = x + i;
            if(nx > 100 || visited[nx]) continue;
            visited[nx] = 1;
            if(!v[nx].size()) q.push({nx,moved + 1});
            else q.push({v[nx][0],moved + 1});
        }
    }
    return ans;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n + m; i++){
        int start,end;
        cin >> start >> end;
        v[start].push_back(end);
    }
    cout << bfs() << '\n';
}

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

2 1
2 60
30 98
65 25

답 : 4

 

input

3 2
10 100
3 93
7 97
95 5
99 9

답 : 2