백준[16928] 뱀과 사다리 게임

BFS를 이용하여 문제에 적힌 규칙을 적용했다.

처음 풀었을 때는 사다리를 만나면 타고 뱀을 타면 무시하는 방법으로 풀었더니 계속 틀렸다.

반례 세 번째 같은 경우가 있어서 뱀을 타고 가는 경우가 있다. 

그 외에는 어려운 부분 없이 쉽게 풀 수 있다.

 

 

#include <bits/stdc++.h>

int slgN, slgM;
struct slgMv{
    int y;
    bool visitied;
}typedef slgMV;

slgMV slgList[101] = {0};
int slgTotalTime = 0;

void slgBFS(){
    queue<pair<int, int>> slgQ;
    slgQ.push({1,1});
    
    int dx[] = {1,2,3,4,5,6};
    
    while(!slgQ.empty()){
        int x = slgQ.front().first;
        int time = slgQ.front().second;
        slgQ.pop();
        
        
        for(int i=0;i<6;i++){
            int mx = x + dx[i];
            
            if(mx == 100){
                slgTotalTime = time;
                return;
            }
            
            if(!slgList[mx].visitied && mx < 100){
                if(slgList[mx].y != 0){
                    slgList[mx].visitied = true;
                    mx = slgList[mx].y;
                }
                
                slgList[mx].visitied = true;
                slgQ.push({mx,time + 1});
                
            }
            
        }
    }
}

void snakeLabberGame(){
    cin>>slgN>>slgM;
    
    // 사다리
    for(int i=0;i<slgN;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        slgList[x].y = y;
    }
    // 뱀
    for(int i=0;i<slgM;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        slgList[x].y = y;
    }
    
    slgBFS();
    
    cout<<slgTotalTime<<endl;
}

 

 

□ 반례

4 1
25 99
5 40
46 77
83 98
66 65

Ans
1 -> 5(40) -> 46(77) -> 83(98) -> 100
= 4

1 5
2 92
94 3
95 4
96 5
97 6
98 7

1 -> 2(92) -> 93 -> 99 -> 100
= 4

2 1
2 60
30 98
65 25

1 -> 2(60) -> 65(25) -> 30(98) -> 100
= 4