[백준/BOJ] 16928 뱀과 사다리 게임 - 접근과 풀이 (c++)

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

16928번: 뱀과 사다리 게임

자바스크립트에 열중한다고 손놓던 백준을 다시...꾸준히 시작해야겠다. kks227 블로그 보면서 풀었던것들이랑, 안풀었던 것들 다시 풀면서 감 익히기.

---

접근방법

100개의 칸, 시작지점부터 목적지까지 도착하는 최소의 횟수. 문제의 분류가 그래프탐색인 걸 알고 있었지만, dp로 풀기에 너무 완벽한 조건이라 dp로 접근을 했다. "dp[idx] = idx번에서 100번 칸까지 도달하는 최소의 횟수"  로 풀면 될 줄 알았다. 그러나 뱀을 타고 내려가는 상황에서, 다른 제약을 걸어주지 않으면 무한루프가 걸릴 것 같았다. 한번 사용한 뱀과 사다리를 dp로 저장하는 등의 추가 변수가 필요한데, 귀찮게 하지말고 다른 방법을 생각하였다.

 

항상 100번칸에 도착할 수 있는 입력만 주어지고, 최소 횟수만 찾으면 되니까, 탐색 깊이만 기억하는 bfs를 하면 된다. 마찬가지로 항상 가능한 입력만 주어지니까 뱀과 사다리를 중복으로 타는 경우가 탐색에 포함되어도 문제가 없다.(최소시간을 찾기위한 최적화-가지치기를 진행한다면 문제가 있을 듯)

 

---

풀이

 tag : bfs

#include<iostream>
#include<queue>
using namespace std;
int N,M;
int warp[101]={0};
int visited[101]={0}; 

int bfs(){
  int depth=0;
  queue<int> q;
  q.push(1);
  visited[1]=1;
  while(!q.empty()){
    int qs=q.size();
    for(int i=0;i<qs;i++){
      int deq=q.front();
      q.pop();
      if(deq==100){
        return depth;
      }
      for(int j=1;j<=6;j++){
        if(visited[deq+j]==0){
          q.push(warp[deq+j]);
          visited[deq+j]=1;
        }
      }
    }
    depth++;
  }
  return 987654321;
}
int main(){
  cin>>N>>M;
  int x,y;
  for(int i=1;i<=100;i++)
    warp[i]=i;
  for(int i=0;i<N+M;i++){
    cin>>x>>y;
    warp[x]=y;
  }
  cout<<bfs();

}