[BOJ 16928] 뱀과 사다리 게임

🔗Link

문제
풀이

💡Idea

• bfs 사용해서 풀이 동일한 가중치의 간선에서 최단 거리를 구하는 상황이기 때문에 적절
• dp를 사용하면 안되는 이유:
  • dp[i]가 i 이전의 상태로만 정의가 안됨.
  • 예를 들면, i보다 큰 값에서 뱀을 타고 내려오면 dp[i]는 i보다 큰 값에 영향을 받게 됨.

    🔑Code

    ```c++ #include <bits/stdc++.h> using namespace std;

#define INF 0x3f3f3f3f

int main(void){ ios_base::sync_with_stdio(0); cin.tie(0);

int N, M, vis[101], ladder[101], snake[101];
fill(vis, vis+101, INF);
fill(ladder, ladder+101, -1);
fill(snake, snake+101, -1);

cin >> N >> M;
for(int i = 0; i < N; i++){
    int x, y;
    cin >> x >> y;
    ladder[x] = y;
}
for(int i = 0; i < M; i++){
    int u, v;
    cin >> u >> v;
    snake[u] = v;
}

queue<int> Q;
Q.emplace(1);
vis[1] = 0;

while(!Q.empty()){
    int cur = Q.front(); Q.pop();
    // 정직하게 한 칸
    for(int i = 1; i <= 6; i++){
        int nxt = cur + i;
        int nxt_vis = vis[cur] + 1;
        if(nxt <= 100){
            // 사다리
            if(ladder[nxt] != -1){
                if(nxt_vis < vis[ladder[nxt]]){
                    Q.emplace(ladder[nxt]);
                    vis[ladder[nxt]] = nxt_vis;
                }
            }
            // 뱀
            else if(snake[nxt] != -1){
                if(nxt_vis < vis[snake[nxt]]){
                    Q.emplace(snake[nxt]);
                    vis[snake[nxt]] = nxt_vis;
                }
            }
            // 일반 칸
            else if(nxt_vis < vis[nxt]) {
                Q.emplace(nxt);
                vis[nxt] = nxt_vis;
            }
        }
    }
}

cout << vis[100];

return 0; } ``` ## 🗨️ Side Notes