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

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

---

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

문제 설명:

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

• n - 1로 이동
• n + 1로 이동
• n * 2로 이동 (이동 시간은 0초)

수빈이가 동생을 찾는 데 걸리는 최소 시간을 출력합니다.

입력:

• 첫째 줄에 정수 n과 k가 주어집니다. (0 ≤ n, k ≤ 100,000)

출력:

• 첫째 줄에 수빈이가 동생을 찾는 최소 시간을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <deque>
using namespace std;

const int MAX = 100001;
int visited[MAX];

void bfs(int start, int target) {
    deque dq;
    dq.push_back(start);
    visited[start] = 0;

    while (!dq.empty()) {
        int current = dq.front();
        dq.pop_front();

        if (current == target) return;

        if (current * 2 < MAX && visited[current * 2] == -1) {
            visited[current * 2] = visited[current];
            dq.push_front(current * 2); // 0초 이동은 우선 처리
        }

        if (current + 1 < MAX && visited[current + 1] == -1) {
            visited[current + 1] = visited[current] + 1;
            dq.push_back(current + 1);
        }

        if (current - 1 >= 0 && visited[current - 1] == -1) {
            visited[current - 1] = visited[current] + 1;
            dq.push_back(current - 1);
        }
    }
}

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

    int n, k;
    cin >> n >> k;

    fill(visited, visited + MAX, -1);

    bfs(n, k);

    cout << visited[k] << '\n';
    return 0;
}

예제

입력:
5 17

출력:
2

입력:
0 100

출력:
7

---

코드 설명

• 0-1 BFS 활용:
  • 가중치가 0인 경우(순간 이동)는 deque의 앞쪽에 삽입하여 우선 처리합니다.
  • 가중치가 1인 경우(이동)는 deque의 뒤쪽에 삽입하여 후순위로 처리합니다.
• 방문 배열:
  • visited 배열에 현재 위치에 도달하는 데 걸린 최소 시간을 저장합니다.
  • -1로 초기화하여 방문 여부를 체크합니다.

시간 복잡도

• BFS의 시간 복잡도는 O(V + E)이며, 최악의 경우 V와 E가 최대 100,001로 매우 효율적입니다.

---

결과

코드는 순간 이동의 가중치가 0이라는 조건을 효과적으로 활용하여 최소 시간을 계산합니다. 0-1 BFS 알고리즘을 통해 대규모 입력에도 효율적으로 동작합니다.

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