[C++] 백준(BOJ) - 17071 : 숨바꼭질 5
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
알고리즘
- 완전탐색
- BFS
- Flood Fill 알고리즘
풀이
- 도착점도 동시에 이동하는 BFS 문제
- 수빈이의 이동 경우의 수는 총 3가지
- 현재 위치 x 기준 / x-1, x+1, x * 2
- 수빈이가 특정 위치 x에 가장 빠르게 도달한 시간이 t라면 t+2, t+4, t+6, … 초 후에도 x에 도달할 수 있다.
- 수빈이가 특정 위치 x에 가장 빠르게 도달할 시간을 홀수, 짝수인 경우로 나누어서 생각한다
- 도달할 시간이 홀수 짝수가 맞지 않으면 만날 수 없다.
- 동생이 홀수 초에 x지점에 도달을 했고, 수빈이가 이전에 홀수 초에 이미 x지점을 방문했다는 것은 동생이 도착한 시점에 다시 x지점에 수빈이가 도착할 수 있다
- 수빈이의 방문처리 배열 값이 이미 true 인 경우가 무조건 turn의 최소 값
코드
// BOJ-17017 : 숨바꼭질 5
#include <bits/stdc++.h>
using namespace std;
const int MAX = 500000; // 50만 * 50만 배열 공간복잡도 너무 크다
int n, k, turn = 1;
bool ok;
int visited[2][MAX+4]; // 수빈이의 이동 배열
// 홀수, 짝수 시간대의 이동만 체크
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
if (n == k) {
cout << 0 << '\n';
return 0;
}
queue<int> q;
visited[0][n] = 1;
q.push(n);
while (q.size())
{
k += turn;
if (k > MAX) break; // 50만 범위 제한
// 2. 수빈이 먼저 도착하고 수빈 도착과 동생 도착의 홀짝이 맞는 경우
if (visited[turn % 2][k])
{
ok = true;
break;
}
// 1. 수빈이가 가면서 동생을 만나는 경우
// Flood Fill 알고리즘 : 층 별로 원하는 값을 미리 할당해놓고 정답에 해당하는 값을 찾아낼 수 있다
int qSize = q.size();
for (int i = 0; i < qSize; i++)
{
int x = q.front();
q.pop();
for (int nx : {x - 1, x + 1, x * 2})
{
if (nx < 0 || nx > MAX || visited[turn % 2][nx]) continue;
visited[turn % 2][nx] = visited[(turn + 1) % 2][x] + 1;
if (nx == k) // 동생이 미리 도착
{
ok = true;
break;
}
q.push(nx);
}
if (ok) break;
}
if (ok) break;
turn++;
}
if (ok) cout << turn << '\n';
else cout << -1 << '\n';
return 0;
}
평가
- 도착점이 고정되어 있는 일반적인 BFS 문제와는 다르게 도착점도 동시에 이동하는 BFS 문제로 도착점인 동생의 값을 turn이라는 변수와 함께 증가 시켜 나가면서 풀이하는 것이 중요했던 문제
- 수빈이가 이동을 진행하면서 동시에 동생을 만나는 경우와 수빈이가 먼저 도착을 한적이 있고 그 후에 동생이 그 위치에 오는 경우 두가지로 나누어서 알고리즘을 구성
- 이 과정에서 visited 배열을 50만 * 50만으로 전부 짤 필요 없이 홀수, 짝수의 개념만 가지고 공간 복잡도를 최소화 할 수 있다
- flood fill 알고리즘
- 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘 (색칠 알고리즘)
- 홀짝으로 visited[2][동생의 위치] 값을 찾아가며 턴별로 q에 담아서 확인하기
