[BOJ 백준] 17071번 : 숨바꼭질 5 (C++)

[BOJ 백준] 17071번 : 숨바꼭질 5 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 동생이 도착하는 시간과 위치를 미리 계산

2. 수진이의 특정 위치에 도달하는 시간을 BFS로 시뮬레이션

3. 동생이 해당 위치에 도착한 시간보다 수진이가 더 빠르거나 같이 도착했고, 도착 시간의 차이가 짝수인 경우 수진이와 동생이 만날 수 있음.

4. +1과 -1을 계속 반복해서 현재 위치에 도착할 수 있는 특성을 이용

5. 현재 위치에 짝수의 횟수로 이동해서 도착한 경우와 홀수의 횟수로 이동해서 도착하는 경우 분리

6. 만나는 경우 중 소요 시간의 최솟값을 구하기 

 

과정

위 문제는 2차원 배열과 BFS를 통해서 문제를 해결할 수 있습니다.

 

1. 동생이 도착하는 시간과 위치를 미리 계산

먼저, 동생 위치는 n초 후에 1부터 n까지 더한 합만큼 이동했으므로, n초 후의 위치를 예측할 수 있습니다.

따라서, n초일 때의 동생 위치를 먼저 계산합니다.

 

이때, 50만 좌표까지만 존재하므로, 50만 좌표 이내의 값일 때만 계산해서 배열에 추가합니다.

 

2. 수진이의 특정 위치에 도달하는 시간을 BFS로 시뮬레이션

 

수진이는 1초마다 -1 , +1, x2 중 하나를 선택해서 이동할 수 있습니다.

그래서, 위 3가지 옵션을 for문으로 돌려, 특정 위치에 도달하는 시간을 기록합니다.

단, 해당 좌표에 제일 처음 도달했을 때가 가장 빠른 시간에 도착한 경우이므로 중복으로 방문하지 않습니다.

 

3. +1과 -1을 계속 반복해서 현재 위치에 도착할 수 있는 특성을 이용

 

수진이는 +1과 -1을 반복해서 현재 위치에 2초마다 다시 도달할 수 있습니다.

그래서, 동생보다 수진이가 빨리 도착한 경우, [동생 도착 시간 - 수진 도착 시간 % 2 == 0] 이면, 수진이와 동생이 서로 만날 수 있습니다.

그러므로, 위 조건을 만족하는 경우 만나는 시간을 [동생 도착 시간]으로 설정하면 됩니다.

 

만약에, 같이 도착하는 경우도 서로의 도착 시간을 빼면, 0이므로 위 조건에 만족하게 됩니다.

 

4. 현재 위치에 짝수의 횟수로 이동해서 도착한 경우와 홀수의 횟수로 이동해서 도착하는 경우 분리

 

수진이가 현재 위치에 짝수번 이동했을 때 도착하는 경우가 있고, 홀수번 이동했을 때 도착하는 경우가 있습니다.

위 조건문만 사용하는 경우에는 현재 위치에 짝수번 이동했을 때 도착과 홀수번 이동했을 때의 도착을 모두 고려하지 못합니다.

 

이는 BFS에서 중복 도착을 고려하지 않기 때문입니다.

만약에, 현재 위치에 동생이 5초에 도착했다고 가정합니다.

 

수진이가 2초와 3초에 해당 위치에 도착한다고 추가로 가정하겠습니다.

그러면, 1차원 배열인 [위치]로만 관리를 하면, 2초에 이미 도착했으므로 3초에 도착하는 수를 무시합니다.

따라서, 2초에 도착한 경우만 고려해 [동생 도착 시간 - 수진 도착 시간]이 홀수가 되어, 수진이와 동생이 만날 수 없다고 판별합니다.

 

그래서, 이를 분리하기 위해 2차원 배열로 [짝수/홀수 번째 이동 구별][위치]를 관리합니다.

[0][위치]는 짝수 번째에 도착하는 시간을 의미하고 [1][위치]는 홀수 번째에 도착하는 시간을 의미합니다.

 

5. 만나는 경우 중 소요 시간의 최솟값을 구하기 

 

위 조건을 만족하는 경우 중, 가장 빨리 만나는 시간을 구하면 됩니다.

 

---

03. 정답 코드

// 플레티넘 5 - 17071번 : 숨바꼭질 5
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

// BFS

// 동생이 n초에 도달하는 위치를 미리 기록

// 수빈이가 특정 위치에 몇 초에 도착하는지 기록
// 동생과 도착 시간이 다를 때, [수빈 도착 시간 < 동생 도착 시간] 이라면,
// 동생 도착 시간 - 수빈 도착 시간 = 짝수일 때, 만나는게 가능
// 수빈 +1-1 반복해서 해당 위치에 도달할 수 있음.

// 해당 위치에 짝수 번에 도달할 때와 홀수 번에서 도달하는 경우가 나눠져 있음.

const int MAX_VALUE = numeric_limits<int>::max();

struct Loc
{
    int x;
    int time;
};

vector<int> g_br_locs;
vector<vector<int>> g_me_locs;

// 동생 위치 찾기
void findBrotherLocations(const int K)
{
    // (1000+1)*500 -> 500'500 -> 50만 이상이므로 1001까지만 처리
    g_br_locs.reserve(1001);
    g_br_locs.push_back(K);

    for(int i = 1; i <= 1000; i++)
    {
        int loc = g_br_locs[i-1] + i;

        // 범위 벗어나는 경우는 무시
        if(loc > 500'000)
            break;

        g_br_locs.push_back(loc);
    }
}

// 본인 위치 찾기
void findMeLocation(const int N)
{
    // [0][위치] : 짝수 번째에 도착하는 가장 빠른 경우
    // [1][위치] : 홀수 번째에 도착하는 가장 빠른 경우
    g_me_locs = vector<vector<int>>(2, vector<int>(500'001, 0));

    queue<Loc> q;
    q.push({N, 0});
    g_me_locs[0][N] = 1;

    while(q.empty() == false)
    {
        const Loc loc = q.front();
        q.pop();

        // 이동
        int nextSeq = (loc.time + 1) % 2;
        for(int i = 0; i < 3; i++)
        {
            int nextLoc = loc.x;
            if(i == 0) nextLoc *= 2;
            else if(i == 1) nextLoc++;
            else nextLoc--;

            // 범위를 벗어나는 경우는 무시
            if((nextLoc >= 0 && nextLoc <= 500'000) == false)
                continue;

            // 이전에 방문한 경우는 무시
            if(g_me_locs[nextSeq][nextLoc] != 0)
                continue;

            // 방문하지 않은 경우에는 진행
            g_me_locs[nextSeq][nextLoc] = g_me_locs[loc.time % 2][loc.x] + 1;
            q.push({nextLoc, nextSeq});
        }
    }
}

// 비교하기
int compareLocs()
{
    int result = MAX_VALUE;
    // 동생 위치와 비교
    for(int seq = 0; seq < 2; seq++)
    {
        for(int time = 0; time < g_br_locs.size(); time++)
        {
            int term = time - (g_me_locs[seq][g_br_locs[time]] - 1);
            //cout << "time : " << time << ", br loc : " << g_br_locs[time] << ", me dest time : " << g_me_locs[g_br_locs[time]] - 1 << ", term : " << term << "\n";
            // 수진이가 먼저 또는 동시에 도착해야 함.
            // 그래서, 항상 0 이상의 자연수가 나와야 함.
            if(term >= 0 && term % 2 == 0)
                result = min(result, time);
        }
    }

    // 동생에게 도달하지 못하는 경우
    if(result == MAX_VALUE)
        result = -1;

    return result;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 수빈 위치 N, 동생 위치 K
    int K, N;
    cin >> N >> K;

    findBrotherLocations(K);
    findMeLocation(N);

    int result = compareLocs();
    cout << result << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!