[백준] 1697 숨바꼭질 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

2. 풀이 과정

• 문제 해결의 흐름
  1.  수빈이의 초기 위치는 N, 동생의 위치가 K로 주어졌을 때 수빈이가 처음 위치 N에서 +1칸, -1칸, *2칸 이동하며 동생의 위치까지 이동한다.
  2.  bfs를 통해 동생의 위치까지 걸리는 최단 시간을 구해야 하므로 방문 배열에 시간을 저장해 주자!
• 나의 코드 

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100001

int N, K; // N : 수빈이의 위치, K : 동생의 위치
int visited[MAX] = {};

int bfs() {
    queue<int> q; 
    q.push(N);
    visited[N] = 0;
    while (!q.empty()) {
        int curPosition = q.front();
        q.pop();

        if (curPosition == K) break;

        int minusPosition = curPosition - 1;
        int plusPosition = curPosition + 1;
        int multiPosition = curPosition * 2;

        // 1. -1
        if (minusPosition >= 0 && visited[minusPosition] == 0) {
            q.push(minusPosition);
            visited[minusPosition] = visited[curPosition] + 1;
        }

        // 2. + 1
        if (plusPosition < MAX && visited[plusPosition] == 0){
            q.push(plusPosition);
            visited[plusPosition] = visited[curPosition] + 1;
        }

        // 3. * 2
        if (multiPosition < MAX && visited[multiPosition] == 0) {
            q.push(multiPosition);
            visited[multiPosition] = visited[curPosition] + 1;
        }
    }

    return visited[K];
}

int main() {
    cin >> N >> K;
    cout << bfs();

    return 0;
}

 

 

---

3. 후기 

 전형적인 bfs 문제였습니다! 숨바꼭질 시리즈 이후 문제들이 기대됩니다!