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

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

13549번: 숨바꼭질 3

백준 사이트의 13549번 문제, 숨바꼭질 3 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

이렇게 짧고 명쾌한 문제가 좋다. 근데 N이 너무 커서 처음에 당황

핵심 포인트

• N이 10만이다. 약 2억번의 연산까지 가능하므로 O(NlogN) 알고리즘 안으로 해결해야 함.
• 최소값을 찾는 프로그램 -> BFS나 Dijkstra 알고리즘
• 순간이동을 하는 경우는 "0초" 소요된다.
• 범위가 0이상이라는 것에 주목하자. 본인은 여기서 많은 고생을 했다.

---

1. 문제풀이 아이디어

• 두 알고리즘 중에 BFS를 선택하기로 하였다.
• 한 싸이클씩 돌려야 하기때문에 현재 큐의 사이즈를 받고, 그 사이즈만큼 연산을 한뒤 시간을 증가 시켰다.
• +1, -1의 경우는 1분이 지나기 때문에 다음 큐에 넣어주고, 2배하는 경우는 시간이 흐르지 않기때문에 큐에 넣어주지 않고 대신 동생의 위치에 도달했는지 체크는 해주어야 한다.
• 중요! N과 K가 0이상인데, 0에 아무리 2배를 해봤자 무한루프만 돌뿐이다.
  • 이 경우를 따로 핸들링 해줄 필요가 있음.

---

2. 코드 핵심 부분

1) BFS 함수 부분,

   아이디어에서 생각한대로 구현하였다.

   while문 안에 큐사이즈만큼 for문으로 묶어서 싸이클을 돌리는 것은 자주 쓰이는 기법이다.

   Floodfill 알고리즘과 맞닿아 있다.

   보면 Now의 범위가 0에 도달하지 않는데, 0이 queue에 들어가는 순간 문제가 생기고,

   main 함수에서 이미 동생이 0인 경우를 핸들링하기 때문에 이를 고려하지 않아도 된다.

void bfs(int st) {

    queue<int> q;
    q.push(st); // 출발 위치를 큐에 삽입

    int visited[100001] = { 0 };
    visited[st] = 1; // 출발 위치 방문 처리

    while (!q.empty()) {

        int cursize = q.size(); // 현재 큐의 사이즈를 구함
        for (int i = 0; i < cursize; i++) { // 현재 큐의 사이즈만큼 반복

            int Now = q.front();
            q.pop();

            while (Now <= 100000) {

                if (Now == K) // 도착 위치에 도달하면 함수를 종료
                    return;

                if (Now < 100000 && !visited[Now + 1]) { // 1초 후에 이동하는 경우
                    visited[Now + 1] = 1; // 방문 처리
                    q.push(Now + 1); // 큐에 추가
                }

                if (Now > 1 && !visited[Now - 1]) { // 1초 후에 이동하는 경우
                    visited[Now - 1] = 1; // 방문 처리
                    q.push(Now - 1); // 큐에 추가
                }

                Now *= 2; // 순간이동을 하는 경우
            }
        }

        Ans++; // 현재까지의 시간을 증가시킴
    }
}

 

2) 메인함수, 그 중에서도 solve 부분을 보자.

   동생이 만약 0의 위치에 있다면 -1을 N만큼 반복해야 도착하므로 바로 출력.

   수빈이가 0의 위치에서 시작한다면 무조건 +1을 처음에 시행해야 한다.

// 메인함수
int main() {

    // input
    input();

    // solve
    if (K == 0) { // 도착 위치가 0인 경우
        cout << N; // 바로 출력
        return 0;
    }
    if (N == 0) { // 출발 위치가 0인 경우
        N++;
        Ans++;
    }

    bfs(N); // bfs 함수 호출

    // output
    output(); // 출력

    return 0;
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// 필요 인자들
int N, K; // 출발 위치 N과 도착 위치 K
int Ans; // 결과값

void input() {
    cin >> N >> K; // N과 K를 입력 받음
}

void bfs(int st) {

    queue<int> q;
    q.push(st); // 출발 위치를 큐에 삽입

    int visited[100001] = { 0 };
    visited[st] = 1; // 출발 위치 방문 처리

    while (!q.empty()) {

        int cursize = q.size(); // 현재 큐의 사이즈를 구함
        for (int i = 0; i < cursize; i++) { // 현재 큐의 사이즈만큼 반복

            int Now = q.front();
            q.pop();

            while (Now <= 100000) {

                if (Now == K) // 도착 위치에 도달하면 함수를 종료
                    return;

                if (Now < 100000 && !visited[Now + 1]) { // 1초 후에 이동하는 경우
                    visited[Now + 1] = 1; // 방문 처리
                    q.push(Now + 1); // 큐에 추가
                }

                if (Now > 1 && !visited[Now - 1]) { // 1초 후에 이동하는 경우
                    visited[Now - 1] = 1; // 방문 처리
                    q.push(Now - 1); // 큐에 추가
                }

                Now *= 2; // 순간이동을 하는 경우
            }
        }

        Ans++; // 현재까지의 시간을 증가시킴
    }
}

void output() {
    cout << Ans; // 결과 출력
}

// 메인함수
int main() {

    // input
    input();

    // solve
    if (K == 0) { // 도착 위치가 0인 경우
        cout << N; // 바로 출력
        return 0;
    }
    if (N == 0) { // 출발 위치가 0인 경우
        N++;
        Ans++;
    }

    bfs(N); // bfs 함수 호출

    // output
    output(); // 출력

    return 0;
}

---

4. 문제 풀이를 마치며..

으아악

처음 문제를 받았을 때는 알고리즘을 어떤걸 사용해야 할지 고민이 되었다.

일단 최소값을 찾는 문제라는 것을 알았는데,

BFS와 Dijkstra중 어느 것을 사용해야 할지 고민이 되었다.

 

BFS는 가중치가 없는(더 정확히는 모두 동일한) 그래프, Dijkstra는 가중치가 있는 그래프에 사용하는데,

두 알고리즘 모두 적용할 수 있을 것 같은 문제였다.

 

더 내가 잘 다루는 BFS 알고리즘을 선택하고 나서는 시간초과가 두려웠는데

x2가 되는 순간이동 때문에 괜찮다고 생각되었다.

 

그렇게 잘 구현했는데 웬걸,

시간초과가 자꾸 발생하는 것이었다.

 

시간 복잡도는 그렇게 크지 않은데 왜 그럴지 고민하다가

K가 0이 되는 경우에 무한루프가 발생하는 것을 발견하였다.

 

그런데도 계속 시간초과가 났다.

왜 N이 0이 되는걸 생각하지 못했지..

 

만약 이게 실제 코딩테스트였다면

와 테스트케이스 전부 통과했다 제출해야지! 했을 것 같다.

 

엣지케이스를 항상 조심하자...