16928번: 뱀과 사다리 게임

문제링크

C++

#include <iostream>
#include <queue>
#include <unordered_map>
#include <cstring>

using namespace std;

int N, M;

unordered_map<int, int> ladder, snake;
queue<int> Q;

int dist[101];

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

    cin >> N >> M;
    int tmp1, tmp2;
    for (int i = 0; i < N; i++){
        cin >> tmp1 >> tmp2;
        ladder[tmp1] = tmp2;
    }
    for (int i = 0; i < M; i++){
        cin >> tmp1 >> tmp2;
        snake[tmp1] = tmp2;
    }

    memset(dist, -1, sizeof(dist));
    dist[1] = 0;
    Q.push(1);
    while (!Q.empty()){
        int tmp = Q.front();
        Q.pop();
        for (int i = tmp + 1; i <= tmp + 6; i++){
            if (i <= 100){
                int value;
                if (ladder.count(i) != 0){
                    if (dist[(value = ladder[i])] == -1){
                        dist[value] = dist[tmp] + 1;
                        Q.push(value);
                    }
                }else if (snake.count(i) != 0){
                    if (dist[(value = snake[i])] == -1){
                        dist[value] = dist[tmp] + 1;
                        Q.push(value);
                    }
                }else if (dist[i] == -1){
                    dist[i] = dist[tmp] + 1;
                    Q.push(i);
                }
            }
        }
    }
    cout << dist[100] << "\n";
}

• '거리'를 보면 BFS / DP 등등을 떠올려보자.
• 키, 밸류에서 키가 겹치지 않으면 unorderd_map을 떠올리자.
• 처음에 while문 내부 if문에서 ladder.count(i) != 0 && dist[ladder[i]] == -1의 조건으로 줘서 사다리가 있는 곳이어도 한 번 방문했던 곳이면 사다리를 타지 않고 사다리의 시작 점을 큐에 넣는 문제점이 발생
  • 조건문 분기 주의해서 작성할 것