[C++] BOJ 17071 / BFS (숨바꼭질 5, 특성 파악하기)

문제 분석

 

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

이전 숨바꼭질 문제에서 동생의 움직임을 추가한 문제이다. 난이도는 Solved.ac 기준 Gold1로 매우 어려운 축에 속한다.

2019 라인플러스 상반기 인터 채용 문제 중에 마지막 문제를 변형시킨 문제이며, 불합을 결정하는 난이도이다.

일단 중요하게 봐야할 부분은 n이 50만으로 크며, 시간 제한이 0.25초라는 점이다. 적절한 분석 및 계획 없이 무턱대고 BFS를 구현하면 시간초과가 뜨기 쉽다.

 

해결 방법

이런 문제를 접하면, 가장 먼저 중요한 특성을 파악하려 노력해야한다. 이 문제에서 가장 중요한 특성은,

어떤 점 x에 t초에 도달할 수 있다면, t+2, t+4, t+6,..에도 x에 도달할 수 있다는 것이다.

즉, 여태 BFS문제를 풀 때 거리 계산을 한 것이 이 문제에서는 시간에 해당하므로, dist[x]를 짝수와 홀수로 구분하여서 구현해야한다. 왜냐면 짝수에 짝수를 더하면 항상 짝수이고, 홀수에 짝수를 더하면 항상 홀수이기 때문이다.

수빈이가 동생보다 dist가 작거나 같으면, 동생을 잡을 수 있다. (본인은 생각을 잘못하여서 dist가 같아야만 잡는다고 생각했었다...)

 

코드

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#define LMT 500000
#define X first
#define Y second
using namespace std;
int dist[LMT+1][2];

int main() {
    queue<pair<int,int>>q;
    int n,k;
    cin >> n >> k;
    
    for(int i=0;i<LMT+1;i++) {	// dist 배열 -1로 초기화
        fill(dist[i], dist[i] +2, -1);
    }
    
    dist[n][0] = 0;	// 시작점은 0초 이므로 짝수칸에 입력
    q.push({n, 0});
    
    // 수빈이 BFS
    while(!q.empty()) {
        pair<int,int> cur = q.front();
        q.pop();
        cur.Y += 1;	// 시간 1초 증가
        for(int nx : {cur.X-1, cur.X+1, cur.X*2}) {
            if(nx<0 || nx > LMT) continue;
            if(dist[nx][cur.Y % 2] != -1) continue;
            dist[nx][cur.Y%2] = cur.Y;
            q.push({nx, cur.Y});
        }
    }
    // 동생 위치 증가시키며 만나는 지점 탐색
    for(int i=0;i<LMT;i++) {
        k += i;
        if(k > LMT) break;
        if(dist[k][i%2] <= i) {
            cout << i;	// 동생이 움직이는 거리와 i 값이 같으므로 i 출력
            return 0;
        }
    }
    cout << -1;

}

 

코드 분석

dist를 홀수와 짝수로 구분하기 위해 2차원 배열로 선언했다. 현재 지점에 도착 시간이 짝수면 [0]에, 홀수면 [1]에 저장되게 구현하였다.

수빈이 먼저 BFS를 전부 돌린 후, 동생은 문제에 주어진대로 시간을 증가시키며, 수빈이의 도착시간보다 늦거나 같으면 해당 시간을 출력시킨 후 종료시켰다.