[백준 #16928 c++] 뱀과 사다리 게임, DP?

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

16928번: 뱀과 사다리 게임

 

이 문제는 DP 유형임을 깨닫고 코드를 적어 제출하기 까지 시간은 얼마 안 걸렸지만 반례를 넘기지 못해서 1시간을 초과해버렸다.

 

뱀과 사다리 게임은 보드게임 중 하나라고 소개돼있다.

1번 칸부터 100번 칸까지 주사위를 굴려서 1~6칸씩 이동하는데

사다리를 만나면 사다리를 타고 여러 칸을 건너뛰지만

뱀을 만나면 뱀을 타고 여러 칸을 다시 돌아온다.

 

주사위로만 이동하면 점화식은 다음과 같다.

i번째 칸으로 갈 때 굴리는 주사위의 최솟값 dp[i]는

 

dp[i] = min(dp[i - 6] + 1, dp[i - 5] + 1, ... , dp[i - 1] + 1) (단, i > 6)

 

로 정의된다.

---

하지만 사다리와 뱀이라는 변수가 있다.

 

나는 여기서 사다리와 뱀을 구분하지 않고 똑같이 '어떤 목적지로 보내버리는 포탈'이라고 여겨서 풀었다.

임의의 1차원 정수 배열 portal을 선언하고 만약 a칸에서 b칸으로 보내버리는 사다리 또는 뱀이 존재한다고 할 때,

 

portal[a] = b

 

식으로 대입을 해주었다.

---

위 사항을 토대로 대충 코드를 짜보면,

dp[1] = 0 으로 놓고,

i = 2 부터 i = 100까지 루프를 돌면서

임의의 i에 대해 portal[i] 가 존재하는 경우

 

dp[portal[i]] = min(dp[portal[i], dp[i])

 

로 놓을 수 있다.

 

portal을 통해 건너뛴 칸으로 이동할 때의 최소 주사위 횟수는 건너뛰기 전 칸의 경우와 동일하다는 의미이다.

---

하지만 여기서는 반례가 존재할 수 있다.

다음 사례를 보자.

 

<입력값>

3 1
23 85
3 52
38 99
54 37

 

<정답>

4

 

평범하게 코드를 돌린다면

1->7->13->19->23=85->91->97->100

총 7번의 주사위를 굴리게 될 것이다.

 

하지만 정답은

1->3=52->54=37->38=99->100

으로 총 4번의 주사위만 굴리면 된다.

 

이 경우는 오히려 뱀을 밟아야 더 기록을 줄일 수 있는 경우에 해당한다.

이미 이 부분에서 DP의 가장 중요한 조건인 '최적 부분 구조'에 어긋난다.

즉, 이 문제는 DP로 풀 수 없다는 얘기다.

DP 배열은 그냥 칸만 만들어 줄 뿐이다.

 

그래서 이 부분을 visit 배열을 통해 다음과 같이 해결했다.

i 칸에서 뱀을 만나 되돌아 가는 경우, 다시 그 칸부터 이후의 값들을 갱신하도록 하였다.

 

if (portal[i] < i && !visit[i]) { // portal[i] < i 의 의미는 현재 칸에서 뱀을 밟았다는 것
     visit[i] = true;
     i = portal[i];
}

---

하지만 또다른 반례가 있다.

다음을 보자.

 

<입력값>

1 5
2 92
94 3
95 4
96 5
97 6
98 7

 

<정답>

4

 

그냥 코드를 돌린다면

1->2=92->94~98->100

으로 총 3번의 주사위를 굴리면 된다고 나올 것이다.

하지만 이는 불가능하다.

 

왜냐하면 94~98를 밟은 순간 반드시 7로 돌아갈 수 밖에 없기 때문이다.

즉, 위 코드에서는 '사다리 또는 뱀을 밟았을 때의 주사위 선택권이 없음'을 간과했다.

 

따라서 실제 정답은

1->2=92->93->99->100

으로 4가 나와야 한다.

 

이를 위해

dp[i] = min(dp[i - 6] + 1, dp[i - 5] + 1, ... , dp[i - 1] + 1) (단, i > 6)

과정에서 루프를 돌며

각 i - 6, i - 5.. i - 1 칸에서 사다리 또는 뱀을 만나는 지 여부를 확인하여 없는 경우에만 최소값을 갱신하도록 하였다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;

int portal[101];
int dp[101];
bool visit[101];
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    fill_n(dp, 101, 1e9);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n + m; i++) {
        int a, b;
        cin >> a >> b;
        portal[a] = b;
    }

    dp[0] = dp[1] = 0;
    for (int i = 2; i <= 100; i++) {
        for (int j = 1; j <= 6 && i - j > 0; j++) {
            if (portal[i - j] == 0)
                dp[i] = min(dp[i], dp[i - j] + 1);
        }
        if (portal[i] != 0) {
            dp[portal[i]] = min(dp[portal[i]], dp[i]);
            
            if (portal[i] < i && !visit[i]) {
                visit[i] = true;
                i = portal[i];
            }
        }
    }

    cout << dp[100];
    return 0;
}

 

 

visit을 적용하고 나서 이 문제가 dp가 아니라 bfs로도 풀 수 있겠구나 싶었다.

과연 다른 문제를 찾아보니 역시 while문과 큐를 사용하여 푼게 있었다.

 

하지만 단순히 i값을 바꿔서 다시 앞에서 부터 루프를 돈다고 해도 애초에 dp이기 때문에 계산량이 적고 100까지 루프를 돌기 때문에 시간, 공간복잡도에는 전혀 지장이 없다.