[BOJ/백준][Silver1] 16928 : 뱀과 사다리 게임 (C++)

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

16928번: 뱀과 사다리 게임

 

 

 

[난이도] Silver1
[유형] BFS

[풀이]
1. 사다리의 위치를 up[사다리의위치]=다음위치 , 뱀의 위치를 down[뱀의위치]=다음위치
와 같이 up,down 두개의 배열에 저장합니다.

2. 위치 1에서부터 BFS를 돌리며 현재 위치에서 k (1~6) 만큼 위로 올라가는 위치를 nxt로 둡니다.

3. up[nxt],down[nxt]가 0이 아니라면 nxt를 그 값으로 수정해줍니다.
문제 조건에 의해 사다리,뱀이 같이 있을 수 없으므로 up[nxt],down[nxt] 둘다 양수인 경우는 없습니다.

4. nxt를 방문하지 않았다면 q에 넣어줍니다. 모든 주사위 값(1~6)에 대해 루프를 돌면서 같은 연산을 해줍니다.

5. q의 front가 100이라면 답을 찾은 것이므로 현재까지 굴린 주사위 횟수를 출력하며 종료합니다.

 

#include <cstdio>
#include <queue>
using namespace std;
int N,M,u,v,up[101],down[101];
bool visit[101];
int main(){
    scanf("%d%d",&N,&M);
    while(N--) scanf("%d%d",&u,&v), up[u]=v;
    while(M--) scanf("%d%d",&u,&v), down[u]=v;

    queue<int> q;
    q.push(1);
    visit[1]=1;
    int ret=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int qf = q.front(); q.pop();
            if(qf==100){
                printf("%d",ret);
                return 0;
            }
            for(int k=1;k<7;k++){
                int nxt = qf+k;
                if(nxt>100) continue;
                int mv=0;
                if(up[nxt]) mv=up[nxt];
                if(down[nxt]) mv=down[nxt];
                if(mv!=0) nxt=mv;
                if(!visit[nxt]){
                    visit[nxt]=1;
                    q.push(nxt);
                }
            }
        }
        ret++;
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/16928.cpp