BOJ 13549 - 숨바꼭질 3(C++) / Team Fortune Drill Week1

https://www.acmicpc.net/problem/13549

문제를 푼 날짜: 2025. 04. 09

#graphs #graph_traversal #bfs #shortest_path #dijkstra #0_1_bfs

내 풀이

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

const int MAX = 100000;



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

    int N, K;
    cin >> N >> K;

    deque<pair<int, int>> dq; // (좌표, 시간)
    vector<bool> visited(MAX + 1, false);  // 방문 체크 배열

    visited[N] = true;

    if(N == K) cout << 0;
    else{
        if (N + 1 <= MAX && !visited[N + 1]) dq.push_back({N + 1, 1});
        if (N - 1 >= 0 && !visited[N - 1]) dq.push_back({N - 1, 1});
        if (2 * N <= MAX && !visited[2 * N]) dq.push_front({2 * N , 0});

        while(1){
            int location = dq.front().first;
            int time = dq.front().second;
            dq.pop_front();
            
            if(visited[location]) continue;
            visited[location] = true;
            
            
            if(location == K){
                cout << time;
                break;
            }
            if(location + 1 <= MAX && !visited[location + 1]) dq.push_back({location + 1, time + 1});
            if(location >= 1 && !visited[location - 1]) dq.push_back({location - 1, time + 1});
            if(location * 2 <= MAX && location < K && !visited[2 * location]) dq.push_front({2 * location , time});
        }
    }
    return 0;
}

---

📌 문제 핵심 요약

• 수빈이는 X에서 출발해서 K로 이동해야 함
• 이동 방식:
  • X-1 또는 X+1로 이동: 1초 소요
  • 2*X로 순간이동: 0초 소요

---

🧠 내가 얻은 인사이트

✅ BFS vs 0-1 BFS

• 초기 접근:
  순간이동과 걷기 모두 1초로 가정하면 일반적인 BFS로 해결 가능 → 큐를 이용한 탐색

• 문제 전환 포인트:
  순간이동이 0초가 되면서, 단순 BFS로는 정확한 최단 시간을 계산할 수 없음
  → 이때 떠올릴 수 있어야 하는 알고리즘:
  ✅ 0-1 BFS
  → 가중치가 0과 1인 경우에 최단 경로를 효율적으로 구할 수 있는 BFS 응용

• 0-1 BFS 구현의 핵심:

  • deque를 사용하고
  • 가중치 0인 이동은 앞(front)에, 가중치 1인 이동은 뒤(back)에 push

---

✅ 디버깅하며 얻은 교훈

• 접근 불가능한 index 체크는 필수
  → location - 1 >= 0, location + 1 <= MAX 등 항상 범위 체크

• visited 배열을 사용하지 않으면 TLE 혹은 무한 루프 발생 가능
  → 같은 위치를 계속 큐에 넣게 됨

• deque에서 언제 pop_front()를 하느냐가 매우 중요
  → visited 체크보다 먼저 pop을 해야 해당 원소가 큐에 남아 무한 반복되는 걸 막을 수 있음

---

💯 코드 클린업 & 개선 팁

1. 시작 위치는 큐에 넣으면서 visited도 동시에 처리

dq.push_back({N, 0});
visited[N] = true;

2. 이동 로직 반복 처리 추상화

for (int next : {location * 2, location - 1, location + 1}) {
    int nextTime = (next == location * 2) ? time : time + 1;

    if (next >= 0 && next <= MAX && !visited[next]) {
        if (next == location * 2)
            dq.push_front({next, nextTime});
        else
            dq.push_back({next, nextTime});
    }
}