뱀과 사다리 게임 백준 16928번 c++

문제 링크 

 

게임판 1차원 배열 board 가 있다. 뱀이나 사다리가 있는 칸만 0이 아닌 값이 있다. 

뱀이나 사다리가 있는 칸은, 목적지 칸 인덱스를 저장하도록 했다.

42칸에 사다리가 있으면 50으로 이동할 때, board[42] = 50 이다. 

 

1의 위치에서 시작하고, 목적지는 100이다. 최소 이동횟수를 구하는 bfs로 푼 코드다. 

 

"맞았습니다" 코드 링크 

숨바꼭질 문제와 비슷하게 느껴졌다. 

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
int answer = 1e9;
int board[102]; // 게임판
bool visited[102]; // 방문 체크

int bfs(){
    queue<pair<int,int>> qu; // <현재위치, 주사위 던진 횟수>
    qu.push({1, 0});
    visited[1] = true;

    while(!qu.empty()){
      pair<int,int> p = qu.front();
      qu.pop();

      int cur = p.first;
      int cur_cnt = p.second;

      if(cur == 100) {  answer = min(answer, cur_cnt); break; }// 목적지 도착

      for(int i = 1; i <= 6; i++){ // 주사위
        int next_cur = cur + i;
        if(next_cur > 100 || visited[next_cur]) continue; // 방문했거나 범위 초과시 지나감
        visited[next_cur] = true;
        
        if(board[next_cur] == 0) qu.push({next_cur, cur_cnt + 1});
        else qu.push({board[next_cur], cur_cnt + 1});
      }
    }
    return answer;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n+m; i++){ // 사다리와 뱀 
    cin >> a >> b; board[a] = b;
  }
  cout << bfs();
  return 0;
}