[백준] 13549 숨바꼭질 3 C++

1. 문제 설명

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

13549번: 숨바꼭질 3

---

2. 풀이 과정

• 문제 해결의 흐름 
  1. ⭐️ bfs를 통해 이 문제를 푼다면 문제의 핵심은 '어쨌든 연산 횟수가 가장 적은 경우가 최단 시간이 된다'이다.
  2.  예를 들어 입력이 1 17이라면 아래와 같이 2가지 경우가 가장 적은 연산 횟수로 동생의 위치에 도달할 수 있는 방법일 것이다. ⭐️따라서 순간이동하는 경우 시간 경과가 0초라고 하더라도 가장 적은 연산 횟수보다 많은 연산을 하며 최단시간이 되지는 못한다!
     • 1 -> 2 -> 4 -> 8 -> 16 -> 17 : 1초 (만약 1 -> 2초가 *2 연산이라면)
     • 1 -> 2 -> 4 -> 8 -> 16 -> 17 : 2초 (만약 1 -> 2초가 더하기 연산이라면)
  3. ⭐️ 이전 문제인 '12851 숨바꼭질 2' 문제와 달리 불필요한 탐색에 있어서 break가 아닌 continue를 해주어야 한다. 
     •  예를 들어 연산 횟수는 같지만 걸리는 시간이 다른 3가지 경우가 있다고 치자. (걸리는 시간 : 1 > 2 > 3이라 가정하자) 
     •  queue에 2 1 3의 순서로 값이 저장되어 있다면 첫 방문 시 2번의 경우가 fasted_time이 되고 1의 경우가 재방문할 때 break문을 사용한다면 실제 최단 시간인 3의 경우에 미치지 못한 채 bfs가 종료되기 때문이다.
     •  즉, cur_position == K를 만족하는 시점 이후에 실질적인 최단 시간이 존재하지만 앞에서 break 하면 뒤의 경우를 탐색하지 못한다!!
• 나의 코드 

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100001

int N, K;
bool visited[MAX];
queue<pair<int, int> > q;

void bfs() {
    q.push(make_pair(N, 0));
    visited[N] = true;
    int result = MAX; // 동생을 찾는 가장 빠른 시간
    bool first_visit = true;

    while (!q.empty()) {
        int cur_position = q.front().first;
        int cur_time = q.front().second;
        q.pop();
        visited[cur_position] = true;

        if (first_visit && cur_position == K) { // 첫 방문
            result = cur_time;
            first_visit = false;
        } else if (!first_visit && cur_position == K && cur_time < result) { // 첫 방문 아닌데 시간 더 적게 나온다면??
            result = cur_time; // 최소 시간 갱신
        } else if (cur_time > result) continue; // 불필요한 탐색은 그만
        // 숨바꼭질_2랑 다른 점임!! 왜냐하면 숨바꼭질_2는 cur_position == K인 시점에서의 동생을 찾는 가장 빠른 시간이 전부 동일하지만
        // 숨바꼭질_3는 서로 다르기에 cur_position == K를 만족한 시점 이후 더 빠른 시간이 존재하지만 앞에서 break하면 그 가장 빠른 시간을 못 찾음

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

        if (minusPosition >= 0 && !visited[minusPosition]) {
            q.push(make_pair(minusPosition, cur_time + 1));
        }

        if (plusPosition < MAX && !visited[plusPosition]) {
            q.push(make_pair(plusPosition, cur_time + 1));
        }

        if (multiPosition < MAX && !visited[multiPosition]) {
            q.push(make_pair(multiPosition, cur_time));
        }
    }

    cout << result; // 수빈이가 동생을 찾는 가장 빠른 시간 출력
}

int main() {
    cin >> N >> K;

    fill_n(visited, MAX, false); // false로 초기화

    bfs();

    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들
  • ⭐️ bfs 내에서 종료 조건을 통해 불필요한 탐색을 줄일 수 있다. 

---

3. 후기 

 뿌듯! 사실 숨바꼭질 2에서 최단 시간이 같더라도 여러 방법이 있다는 정보를 얻어서 그런지 쉽게 풀렸다!