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

문제 링크 : www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

간만에 추억의 게임이 언급되어 마음을 훈훈하게 만드는 문제였다.

 

문제 풀이는 다음과 같다. 

 

1. 먼저 필요한 변수들을 선언한다. 전역변수이건 지역변수이건 상관없다.

int n,m,x,y,u,v,pos,num,npos,nnum,ans,up[101],down[101],cnt[101];
bool ch[101];

일부로 문제에서 요구하는 사항들을 그대로 맞추다보니 선언한 변수들이 많아졌는데, 핵심적인 변수들은 다음과 같다. 

bool ch[101] = 방문여부 판단, int up[101] = 올라가는 사다리

int down[101] = 내려가는 사다리, int cnt[101] = 해당 지점에 최소 주사위 운용 횟수

 

2. 필요한 값을 모두 입력, 저장하고 큐를 구현해준다.

큐는 현재 위치와 누적 주사위 운용 횟수를 저장해야하기 때문에 pair<int,int>형으로 구현한다.

    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        up[x] = y;
    }
    for(int i=0; i<m; i++){
        cin >> u >> v;
        down[u] = v;
    }
    queue<pair<int,int>> q;
    q.push({1,0});
    // ch[1] = true;
    // cnt[1] = 0;

while문에 들어가기전에 ch[1]과 cnt[1]을 각각 true, 0으로 저장해도 되지만, 저장하지 않아도 무방하다. 

이 주사위 게임은 1과 100에 어떠한 사다리와 뱀이 연결되어있지 않아, 다시 1로 돌아갈 일이 없기 때문이다.

또한 주사위는 1~6의 숫자만 나와 앞으로 나아가기 때문에 더더욱 해당 배열의 값을 저장할 필요가 없다.

 

3. 아래 while문을 대략적으로 훑고 하나씩 세세히 이해해보자.

    while(!q.empty()){
        pos = q.front().first; // 1
        num = q.front().second;
        q.pop();
        if(pos==100){
            cout << num << "\n";
            exit(0);
        }
        for(int i=6; i>=1; i--){ // 2
            npos = pos+i;
            nnum = num+1;
            if(npos<=100&&!ch[npos]){ // 3
                ch[npos] = true;
                cnt[npos] = nnum;
                if(up[npos]) { // 4
                    npos = up[npos];
                    cnt[npos] = nnum;
                }
                else if(down[npos]){ // 5
                    npos = down[npos];
                    cnt[npos] = nnum;
                }
                ch[npos] = true; // 6
                q.push({npos,nnum});
            }
        }
    }

(1) pos와 num에 큐의 맨 앞에 위치한 값들을 각각 저장해주고 큐를 pop해준다.

만약 현재 지점을 의미하는 pos가 100일 경우, 곧 바로 누적 주사위 운용 횟수를 출력하고 종료해준다.

참고로 문제에서 '무조건 100에 도달할 수 있다'라고 언급했기 때문에, while문 내부에서 무조건 코드는 종료된다.

 

(2) 주사위는 1~6부터 값이 나온다. 때문에 1~6의 숫자를 for문으로 돌리면 된다.

이때 npos는 현재 위치에서 + 주사위 i값을 더한 새로운 위치값이 되며, nnum은 현재 누적 주사위 운영 횟수 + 1을 더한 새로운 누적 횟수가 된다.

 

(3) 새로운 위치값이 100 이하이고 아직 해당 지점을 방문한 적이 없다면 해당 지점을 방문했다고 표시해주고, 동시에 해당 지점의 누적 주사위 운영횟수를 업데이트 해준다.

 

(4) 이 코드는 만약 해당 지점에 사다리가 설치되어있을 경우에 해당되는 부분이다. 사다리가 설치되어있으면 사다리를 타고 이동한 지점을 새로 갱신해준다. 이때 사다리를 타고 새로 이동한 지점의 누적 주사위 운영횟수도 업데이트하는걸 잊지 말자.

 

(5) 이 코드는 반대로 뱀이 설치되어있을 경우이다. 뱀이 있을 경우 뱀을 타고 이동한 지점을 새로 갱신해준다. 동시에 새로 이동한 지점의 누적 주사위 운영횟수를 업데이트하는걸 잊지 말자.

 

(6) (4)~(5)에 해당되는 경우를 고려하여, 마지막으로 다시 한번 새로 이동한 지점의 방문 여부를 체크해준다. 그리고 큐에 새로운 위치와 누적 주사위 운영횟수를 저장해준다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n,m,x,y,u,v,pos,num,npos,nnum,ans,up[101],down[101],cnt[101];
bool ch[101];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        up[x] = y;
    }
    for(int i=0; i<m; i++){
        cin >> u >> v;
        down[u] = v;
    }
    queue<pair<int,int>> q;
    q.push({1,0});
    while(!q.empty()){
        pos = q.front().first;
        num = q.front().second;
        q.pop();
        if(pos==100){
            cout << num << "\n";
            exit(0);
        }
        for(int i=6; i>=1; i--){
            npos = pos+i;
            nnum = num+1;
            if(npos<=100&&!ch[npos]){
                ch[npos] = true;
                cnt[npos] = nnum;
                if(up[npos]) {
                    npos = up[npos];
                    cnt[npos] = nnum;
                }
                else if(down[npos]){
                    npos = down[npos];
                    cnt[npos] = nnum;
                }
                ch[npos] = true;
                q.push({npos,nnum});
            }
        }
    }
    return 0;
}