백준 1697번 [숨바꼭질](C++) -yes6686- 티스토리

백준 문제 풀이: 1697 [숨바꼭질]

---

문제 링크: https://www.acmicpc.net/problem/1697

문제 설명:

수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있습니다. 수빈이는 1초 후에 다음 중 하나의 행동을 할 수 있습니다:

• 현재 위치에서 1만큼 앞으로 이동
• 현재 위치에서 1만큼 뒤로 이동
• 현재 위치의 2배 위치로 순간이동

수빈이가 동생의 위치 K로 이동하는 데 걸리는 최소 시간을 구하세요.

입력 조건:

• 첫째 줄에 N과 K가 주어집니다. (0 ≤ N, K ≤ 100,000)

출력 조건:

• 수빈이가 동생의 위치 K로 이동하는 데 걸리는 최소 시간을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int n, k;
int visited[100001]; // 방문 여부와 최소 시간을 저장
queue<int> q;

void bfs(int start) {
    q.push(start);
    visited[start] = 0; // 시작점은 0초

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        // 동생의 위치에 도달하면 종료
        if (curr == k) break;

        // 이동 가능한 경우 탐색
        if (curr - 1 >= 0 && visited[curr - 1] == -1) {
            visited[curr - 1] = visited[curr] + 1;
            q.push(curr - 1);
        }
        if (curr + 1 <= 100000 && visited[curr + 1] == -1) {
            visited[curr + 1] = visited[curr] + 1;
            q.push(curr + 1);
        }
        if (curr * 2 <= 100000 && visited[curr * 2] == -1) {
            visited[curr * 2] = visited[curr] + 1;
            q.push(curr * 2);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    // 방문 배열 초기화
    fill(visited, visited + 100001, -1);

    bfs(n);

    // 결과 출력
    cout << visited[k] << '\n';
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 BFS를 사용하여 수빈이가 동생 위치로 이동하는 데 걸리는 최소 시간을 구합니다.

• 입력 처리:
  • `n`은 수빈이의 초기 위치, `k`는 동생의 위치입니다.
• BFS 탐색:
  • 큐에 현재 위치를 추가하며 시작합니다.
  • 현재 위치에서 가능한 이동 (앞으로 1, 뒤로 1, 순간이동)을 탐색합니다.
  • 방문하지 않은 위치는 현재까지 걸린 시간 +1로 갱신합니다.

시간 복잡도 분석:

• 최대 100,001개의 위치를 방문하며 BFS를 수행하므로 O(V + E) = O(100,001).

입력의 크기가 제한되어 있으므로 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5 17

출력:
4

입력:
0 100

출력:
7

수빈이가 동생 위치로 이동하는 최소 시간이 정확히 출력됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!