백준 16928번 뱀과 사다리 게임

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

 

해당칸에 도착하는 최소 횟수를 dp값으로 하였을때

사다리는 이전 dp값을 가져오면 돼서 문제가 없지만

뱀은 dp 진행 방향을 역행하기 때문에 문제가 발생한다.

이를 위해 뱀을 타고 내려가서 다시 최적화 하는 방법이 있다.

해당 부분을 고려하여 뱀을 타서 최소값이 갱신된다면 해당 지점에서 다시 진행하도록 했다.

 

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;

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

    int x, y;
    int dp[101];
    unordered_map<int, int> ledderIn;	// 키-값이 사다리 출발-도착
    unordered_map<int, int> ledderOut;	// 키-값이 사다리 도착-출발
    unordered_map<int, int> snake;
    
    // 입력
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        ledderIn.emplace(x, y);
        ledderOut.emplace(y, x);
    }
    for(int i=0; i<m; i++){
        cin >> x >> y;
        snake.emplace(x, y);
    }
    
    // 기본값 넣기
    for(int i=2; i<=7; i++)
        dp[i]=1;
    
    // dp
    for(int i=8; i<=100; i++){
        vector<int> pre;	// 최솟값 후보 저장
        
        // 이전 6칸중 사다리나 뱀의 출발부가 아닌 칸이 최솟값 후보가 됨
        for(int j=6; j>0; j--)
        	if(!ledderIn.count(i-j) && !snake.count(i-j))
        		pre.push_back(dp[i-j]+1);
                
        // 해당칸이 사다리 도착 지점이라면 사다리 출발 지점의 dp값도 최솟값 후보
        if(ledderOut.count(i)) pre.push_back(dp[ledderOut[i]]);
        dp[i]=*min_element(pre.begin(), pre.end());
		
        // 뱀칸일때 dp값이 출발지점 < 도착지점 이면 최솟값 갱신 후 도착 지점에서 다시 출발
        if(snake.count(i) && dp[i] < dp[snake[i]]){
            dp[snake[i]] = dp[i];
            i = snake[i];
        }
    }

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

 

1. 사다리와 뱀의 출발-도착을 해시맵(unordered_map)에 저장한다. (이때 사다리는 도착-출발 해시맵도 만든다.)

2. dp를 돌릴때 이전 6칸중 사다리나 뱀의 출발칸은 최솟값 후보에서 제외한다.

3. 해당칸이 사다리 도착칸이면 출반칸의 dp값도 최솟값 후보가 된다.

4. 최솟값을 구한 후 해당 칸이 뱀칸이라면 도착지점의 최솟값과 비교한다.

5. 해당 칸이 더 작다면 도착칸을 갱신하고 도착칸부터 다시 출발한다.