백준 16928 뱀과 사다리 게임

백준 16928 - 뱀과 사다리 게임

---

오늘은 트리, DFS? 문제 뱀과 사다리 게임 문제를 풀었다. 평상시 하던 dfs랑 똑같은 문제였는데 계속 틀리고 오래 걸린다.
속상하다.
먼저, 뱀이나 사다리가 있는 경우에만 트리로 만들어 주기로 하였다. 그냥 +1, +2 .. +6 씩 순차적으로 증가하는 이동의 경우는 따로 관리해 줄 필요가 없다.

계속 틀리게 나온 이유는 내가 다리를 타고 이동한 값을 큐에 계속 넣어주었던것이 원인이었는데, 넣어주어야 하는것이 당연히 맞지만
나같은 경우는 이동 전 값도 큐에 넣어주었단 거였다. 예를 들어 12번에서 98번으로 다리가 있었다면,
나같은 경우는 98을 큐에 넣고 12도 큐에 넣어주었는데, 그랬기 때문에 문제가 발생하였다.

주사위를 1~6까지 이동하며, cur + 1, cur +2 .. 의 값을 계속 table에서 다리가 있는 칸인지 확인해 존재한다면 다리를 이동한 값을 큐에 넣어주고, cur + i 값은 넣어주지 않는게 중요하다!

while (!q.isEmpty()) {
            int cur = q.peek();
            q.remove();
            for (int i = 1; i <= 6; i++) {
                int n_c = cur + i;
                if (n_c == 100) {
                    System.out.println(visited[cur]);
                    return;
                }
                else if (n_c < 100) {
                    if (table.get(cur + i).size() == 1) {
                        n_c = table.get(cur+i).get(0);
        q.add(n_c);
        }
        if (visited[n_c] == 0) {
                        visited[n_c] = visited[cur] + 1;
                    }
                }
            }
        }