[Algorithm] Baekjoon 16928번 : 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

 

 
struct Node
{
    int num;
    int count;
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, m;
    int x, y; // x < y
    int u, v; // u > v
    map<int, int> routes;
    bool visited[101] = { false };
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y; 
        routes[x] = y;
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v;
        routes[u] = v;
    }
 
    queue<Node> q;
    q.push({ 1,0 });
    int answer = 1000000;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curNum = curNode.num;
        int curCount = curNode.count;
 
        if (curNum == 100)
        {
            cout << curCount;
            break;
        }
        
        for (int i = 1; i <= 6; i++)
        {
            int nextNum = curNum + i;
 
            if (nextNum > 100) continue;
            
            if (routes[nextNum] && !visited[nextNum])
            {
                visited[nextNum] = true;
                q.push({ routes[nextNum], curCount+1 });
                continue;
            }
 
            if (routes[nextNum] && !visited[nextNum])
            {
                visited[nextNum] = true;
                q.push({ routes[nextNum], curCount+1 });
                continue;
            }
 
            if (!visited[nextNum])
            {
                visited[nextNum] = true;
                q.push({ nextNum, curCount + 1 });
            }
        }
    }
 
    return 0;
}
 
 
 

뭔가 설명이 이것저것 써져있긴 한데, 결국 칸마다의 상태는 총 3개가 있고 반드시 한개의 상태만이 존재한다.

사다리이동하는 칸이거나, 뱀이동을 하는 칸이거나, 그냥 평범한 이동을 하는 칸이거나.

그래서 처음 인풋으로 주어지는 사다리와 뱀이동의 정보에 관해서 맵변수를 따로 선언해서 하긴 했었는데, 어차피 하나의 상태만이 존재하기 때문에 변수 하나로 둘 다 입력을 받았다.