백준 16928 - 뱀과 사다리 게임 - BFS

문제

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

풀이전략

1. 같은 곳은 이동할 수 없다. 왜냐하면 아무리 뱀과 사다리를 타더라도 같은 곳을 다시 이동한다면 결국 무한루프에 빠지기 때문이다. 따라서 같은 곳은 이동할 수 없기 때문에 ch배열로 중복된 곳을 체크한다.
2. 처음에 DFS로 가능하다고 생각했지만 BFS로 풀어야한다.
3. 그래프 문제와 동일하게 생각하면 된다. 물론 주사위로도 움직일 수 있지만, 그외에 사다리와 뱀의 경우는 그래프의 간선처럼 계산하면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

int dp[101];
int snake[101];
bool ch[101];
int N, M;
const int MAX = 2147000000;


int BFS(){
    queue<pair<int, int> > q;
    q.push(make_pair(1, 0));

    while(!q.empty()){
        int n = q.front().first;
        int L = q.front().second;
        q.pop();
        if(n == 100) return L;
        for(int i=1; i<=6; i++){
            int next = n+i;
            if(next>100) continue;
            if(snake[next] != -1){
                next = snake[next];
            }
            if(!ch[next]){
                ch[next] = true;
                q.push(make_pair(next,L+1));
            }
            
        }
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N >> M;
    int ta, tb;
    memset(dp, -1, sizeof(dp));
    memset(snake, -1, sizeof(snake));
    for(int i=1; i<=N+M; i++){
        cin >> ta >> tb;
        snake[ta] = tb;
    }

    // cout << DFS(0,1) << endl;
    cout << BFS() << endl;
    return 0;
}

소감

처음에 DFS로 풀려고해서 좀 많이 헤메였다. 앞으론... 최단거리라고하면 일단 BFS로 시작해야겠다.