[백준] 17071 숨바꼭질 5 C++

1. 문제 설명

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

17071번: 숨바꼭질 5

---

2. 풀이 과정

• 문제 해결의 흐름 
  1.  일단 단순하게 구현해보자. 이동할 때마다 1씩 증가되는 현재 이동 시간, curTime값을 통해 현재 동생의 위치 cur_K의 값을 갱신해주자. 
  2.  예제로 17 5의 입력이 들어왔을 때를 생각해보자. 동생의 위치를 찾는 과정을 다음과 같다. 이때, 이전에 풀었던 숨바꼭질 1~4의 방식대로 방문처리해준다면 15 -> 14 -> 15의 방법으로 이동할 수 없다. 그렇기에 방문처리를 하지 않고 bfs를 구현하였다. 

curPosition	17	16	15	14	15
curTime	0	1	2	3	4
curK	5	6	8	11	15

           3. 그러나 역시 메모리 초과! 3개의 if문을 거치며 queue에 새로운 값을 추가하기에 밑이 3인 지수 시간 복잡도를 거치기 때문이다.

           4. ⭐️ 문제의 키포인트는 방문처리를 어떻게 해주냐는 것인 듯하다! 다른 예제를 통해 문제를 좀 더 깊이 이해해보았다.

           ex) 입력이 16 50일 때...

curPosition	16	32	64	65	64	65
curTime	0	1	2	3	4	5
curK	50	51	53	56	60	65

•  사실상 curTime = 3일 때, 65의 위치에 도착하였지만 동생을 위체 2초동안 수빈이가 제자리 뛰기한 느낌이다! 생각해보니 동생이 65의 위치에 5초에 도착하던 7초에 도착하던 11초에 도착하던 제자리 뛰기한다면 만날 수 있을 것이라는 생각이 들었다!!!
• ⭐️ 문제의 키포인트 : curTime이 홀수일 때와 짝수일 때를 나누어 도달한 위치값을 전부 저장해주자. 이후 동생의 위치가 이전에 수빈이가 방문했던 적이 있던 곳이라면 수빈이는 제자리 뛰기만 하면 되니 만날 수 있다! 

• 나의 코드 

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

#define MAX 500001

int N, K; // N : 수빈이의 위치, K : 동생의 위치
int visited[2][MAX] = {}; // 전부 0으로 초기화

struct val {
    int position;
    int time;
    int K_val;
};

int bfs() {
    queue<val> q;
    val first_val = {N,0,K}; // [시작] 위치 : N, 시간 : 0, K의 값 : K
    q.push(first_val);
    visited[0][N] = 1;
    int flag;

    while (!q.empty()) {
        int curPosition = q.front().position;;
        int curTime = q.front().time;
        int curK = q.front().K_val;
        q.pop();

        if (curK >= MAX) return -1; // 아직 못 찾았다면 -1

        if (visited[curTime%2][curK] == 1) return curTime; // 이전에 찾은 적이 있다면 현재 시간 출력

        if (curTime%2 == 0) flag = 1; // 현재 시간은 짝순데 저장되는 값은 홀수
        else flag = 0;               // 현재 시간은 홀순데 저장되는 값은 짝수


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

        curK += curTime + 1;

        // 1. -1
        if (minusPosition >= 0 && visited[flag][minusPosition] == 0) {
            val minus_val = {minusPosition, curTime + 1, curK};
            q.push(minus_val);
            visited[flag][minusPosition] = 1;
        }

        // 2. + 1
        if (plusPosition < MAX && visited[flag][plusPosition] == 0) {
            val plus_val = {plusPosition, curTime + 1, curK};
            q.push(plus_val);
            visited[flag][plusPosition] = 1;
        }

        // 3. * 2
        if (multiPosition < MAX && visited[flag][multiPosition] == 0) {
            val multi_val = {multiPosition, curTime + 1, curK};
            q.push(multi_val);
            visited[flag][multiPosition] = 1;
        }
    }
    return -1;

}

int main() {
    cin >> N >> K; // 입력 받기
    if (N == K) cout << 0;
    else cout << bfs();

    return 0;
}

• 이 문제를 통해 얻어갈 수 있는 것들
  • 예제를 통한 문제 이해가 안되면 문제를 해석할 수 없다. 

---

3. 후기

 플레 문제 처음 풀어봐서 뿌듯하다! 플레 난이도부터는 더 깊은 사고 능력을 요구하는 듯하다.