baekjoon 16928:뱀과 사다리 게임

baekjoon 16928 뱀과 사다리 게임

16928 뱀과 사다리 게임

접근

처음엔 dp로 풀고자 했다. \(dp(i) = 1 + min(\sum_{k=1}^{6}dp(i+k))\) 이런식으로 말이다.
그리고 a –> b로 가는 사다리가 있으면
dp(a) = dp(b)
이런식으로 예외처리 하면 될 줄 알았다. 하지만 이렇게 되면 사이클이 있는 그래프에서 dp를 적용하게 되는데
그렇기 때문에 두 노드가 서로를 의존하는 상황이 발생하면서
사람이라면 방정식을 풀어 해결할 수 있지만
컴퓨터는 둘 중 하나가 정해지지 않으면 재귀로는 풀리지 않는 상황이 발생해서
꼬이게 되는 현상을 발견했다.
그래서 최단거리 문제니까 bfs로 풀리겠다 싶었다.

뱀과 사다리는 a –> b라면 b가 연결된 node를 모두 a에서도 연결되게 하는 방식으로 해결했다.

코드

#include <iostream>
#include <queue>

using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  //let no jump jump

  int graph[100][100];
  for(int i = 0; i < 100; i++){
    for(int j = 0; j < 100; j++){
      graph[i][j] = 0;
    }
  }
  int visited[100] = {0, };
  int distance[100] = {0, };
  for(int i = 0; i < 100; i++){
    for(int j = i+1; j <= i+6; j++){
      if(j >= 100) break;
      graph[i][j] = 1;
    }
  }
  int n, m; cin >> n >> m;
  int t = n+m;
  while(t--){
    int a, b; cin >> a >> b;
    a--; b--;
    for(int i = a + 1; i <= a+6; i++){
      if(i >= 100) break;
      graph[a][i] = 0;
    }
    for(int i = b + 1; i <= b+6; i++){
      if(i >= 100) break;
      graph[a][i] = 1;
    }
  }
  //graph made
  queue<int> q;
  q.push(0);
  visited[0] = 2;
  while(!q.empty()){
    int cur = q.front();
    q.pop();
    for(int i = 0; i < 100; i++){
      if(graph[cur][i] == 1 && visited[i] == 0){
        visited[i] = 1;
        q.push(i);
        distance[i] = distance[cur] + 1;
      }
    }
    visited[cur] = 2;
  }
  cout << distance[99] << "\n";
  
  
  
  return 0;
}

다르게 푸는 법

크기가 크지 않아서 인접 행렬로 풀어서 \(O(V^2)\)에 풀었는데
\(O(V+E)\)에 풀 걸 그랬다.

배운 점

bfs로 최단거리 구하는 법을 구현해 보았다.