BOJ 1697 숨바꼭질 c++

백준 1697 숨바꼭질 문제 cpp

 

BFS 문제 풀이방식으로 해결.

 

시작지점을 기준으로 -1 지점, +1 지점, *2 지점인 곳에 1씩 더해가며 답을 찾음.

범위를 벗어나는 경우 (0 미만 혹은 100000이 넘어가는 경우.) continue 를 꼭 해줘야 함.

 

 

 

사진 출처 - img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fk.kakaocdn.net%2Fdn%2FvwJ4M%2FbtqD4xSR4eQ%2Fg7qbBDkq5xnTsvjk5hhAo0%2Fimg.png

 

 

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

int board[200002];
int n, m;
int dx[] = {-1, 1, 2};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    queue<int> Q;
    for (int i = 0; i < 200002; i++) {
        board[i] = -1;
    }
    board[n] = 0;
    Q.push(n);
    while (board[m] == -1) {
        int cur = Q.front();
        Q.pop();
        for (int dir = 0; dir < 3; dir++) {
            int nx;
            if (dir != 2)
                nx = cur + dx[dir];
            else
                nx = cur * dx[dir];
            if (nx < 0 || nx > 100000)
                continue;
            if (board[nx] >= 0)
                continue;
            board[nx] = board[cur] + 1;
            Q.push(nx);
        }
    }
    cout << board[m];
}