16928번 뱀과 사다리 게임

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

굉장히 쉬운 문제인줄 알았다.

그런데 계속 틀리길래 생각보다 좀 고민했다.

틀린 이유

1. 66번 째 줄의 continue;를 안 써준 것

→ 예를 들어 2에서 98로 갈 수 있을 때, 1 → 2 → 98이 하나의 과정이기 때문에 98만 Queue에 push하면 된다. 굳이 2까지 Queue에 push할 필요가 없었다. 즉, 둘 중 하나만(뱀, 사다리의 이동 또는 단순 주사위의 이동) push 해야함.

2. 처음에 61번 째 줄에 if (move != -1 && !visit[move])로 썼었음

→ !visit[move]를 쓸 필요가 없었다. 뱀이나 사다리로 통해 더 최소한의 방법으로 이동할 수도 있기 때문이다. 즉, BFS와 뱀과 사다리의 조건 때문에 다시 이용할 수 있기 때문이다. 만약 원래대로 썼다면 뱀과 사다리는 한 번 테스트 후 소멸되기 때문에 BFS에 어긋난다. 조건문은 57번 째 줄의 if 조건문만으로도 충분하다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, M = 0;
 
vector<pair<int, int> > v;
 
bool visit[101] = { false, };
 
queue<int> q;
 
int go(int get)
{
    for (int i = 0; i < v.size(); i++) if (v.at(i).first == get) return v.at(i).second;
            
    return -1;
}
 
int BFS()
{
    q.push(1);
    visit[1] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int now = q.front();
 
            q.pop();
 
            if (now == 100) return ret;
 
            for (int i = 1; i <= 6; i++)
            {
                int next = now + i;
 
                if (next <= 100 && !visit[next])
                {
                    int move = go(next);
 
                    if (move != -1)
                    {
                        q.push(move);
                        visit[move] = true;    
 
                        continue;
                    }
 
                    q.push(next);
                    visit[next] = true;
                }
            }
        }
 
        ++ret;
    }
}
 
int main(void)
{
    int from = 0, to = 0;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N + M; i++)
    {
        scanf("%d %d", &from, &to);
 
        v.push_back({ from, to });
    }
 
    printf("%d\n", BFS());
 
    return 0;
}