백준 16928 뱀과 사다리 게임 c++ // dp불가능한경우, bfs복습

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

1. dp불가능한경우

1. dp는 단방향이고 사이클이 없는 그래프에서만 사용가능하다!

 이문제의경우 뱀을만나는경우 뒤로돌아가기때문에 양방향이다!! ->  dp 불가

 

2. dp 주의점

그럼에도 불구하고 dp로 짤때 실수를 많이 했는데,

시행착오를 고쳐보자

1. 의사코드(그래프)

dp는 끝에도달(100)하면 그때 중 최소값을 골라(v표시)가는 알고리즘이다.

이때, 98에서 dp=dfs이렇게 저장을 해줘야 "1"값이 저장되어 12로 그대로 전달된다.

기존 : dfs만 돌려줬더니 dp초기값인 0이 12번노드로 리턴됬다....

 

 

3. 전체코드 dp(오답)

오답인이유 : dp는 해당상태를 재탐색하지 않는 알고리즘인데,

뱀을타고 역방향으로 이동하는경우 재탐색하면 더 나은 최적해가 있다!!

#include <bits/stdc++.h>

using namespace std;

int n,m;
int sa[101], snake[101],dp[101];

int dfs(int cur) {
    //cout << cur << " ";
    if (cur > 100) return 1e9;

    if (cur == 100) {
        //cout << "\n";
        return 0;
    }

    if (dp[cur] != -1) return dp[cur];


    dp[cur] = 0;
    if (sa[cur]) {
        dp[cur] = dfs(sa[cur]); //!dp에 넣어줘야함!
        //return dp[sa[cur]];
    }
    if (snake[cur]) {
        dp[cur] = dfs(snake[cur]);
        //return 1e9; //뱀있는경로는 제외하는게 최적이다 -> 아님
    }


    //!사다리가없고 뱀이없는경우만 !
    if(sa[cur]==0 && snake[cur]==0)
        dp[cur] = min({ dfs(cur + 1) + 1 , dfs(cur + 2) + 1 ,  dfs(cur + 3) + 1 , 
         dfs(cur + 4) + 1 ,  dfs(cur + 5) + 1 ,  dfs(cur + 6) + 1 });
    return dp[cur];
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n>>m;
    for (int i = 0; i < n; ++i) {
        int a,b;
        cin >> a>>b;
        sa[a] = b;
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        snake[a] = b;
    }
    memset(dp, -1, sizeof(dp));

    cout<<dfs(1);

    return 0;

}

 

4. bfs복습

0. 초기값, 방문처리

while(q.size()){
1. 종료조건
    2.nxt계산
    3.범위,조건 체크
    4. vis[nxt]=vis[cur]+1
}

 

5. 전체코드

#include <bits/stdc++.h>

using namespace std;

int n,m;
int sa[101], snake[101],vis[101];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n>>m;
    for (int i = 0; i < n; ++i) {
        int a,b;
        cin >> a>>b;
        sa[a] = b;
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        snake[a] = b;
    }
   
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (q.size()) {
        int cur = q.front(); q.pop();
        //!종료조건은 맨위에!
        if (cur == 100) { //!bfs특 : 첫도착이 최적값임!
            cout << vis[cur]-1; //초기값을 1로뒀기땜에 -1해야함
            return 0;
        }

        for (int i = 1; i <= 6; ++i) {
            int nxt = cur + i; //1. nxt계산
            if (vis[nxt]) continue;
            if (nxt > 100) continue;
            if (sa[nxt]) { //2. 뱀, 사다리인 경우 nxt를 재계산해야함!
                nxt = sa[nxt];
            }
            if (snake[nxt]) {
                nxt = snake[nxt];
            }
            if (vis[nxt]) continue;
            q.push(nxt);
            vis[nxt] = vis[cur] + 1; //!nxt!를 방문처리 + 정답갱신!
        }
    }

    return 0;

}