1. 문제 이해 단계
https://www.acmicpc.net/problem/12851
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
X좌표로만 이루어진 맵이 존재한다.
출발점 N과 도착점 K가 입력으로 들어온다.
출발점 N에서 할 수 있는 움직임은 총 3개이다.
1. X+1
2. X-1
3. X*2
3개의 움직임을 적절히 조합해서 도착점 K까지 갈 수 있는 가장 빠른 시간을 구하고,
가장 빠른 시간으로 갈 수 있는 경우의 수를 출력하는 문제
2. 문제 접근 단계
숨바꼭질 시리즈 문제이다.
일단 제한조건부터 살펴보면
좌표는 최대 100,000까지 가능하다.
만약 O(N^2)으로 문제를 푼다면
10^10으로 시간초과가 뜬다는 것을 유의하자.
2.1. 유형 분석
일단 이 문제는 어떤 유형의 문제일까?
찾아야 하는 것은 출발지에서 도착점까지의 가장 빠른 시간과 그때의 경우의 수이다.
여기서 결국 시간은 거리라고 볼 수 있기 때문에
최단경로라고 봐도 무방하다.
움직임이 정해져 있고, 맵에서 하나의 목표물을 최단거리로 목적지까지 움직이는 것이다.
그래서 이 문제는 일단 BFS(우선너비탐색)을 사용하는 것이 낫다는 판단을 했다.
일반적인 BFS를 사용하면 최단거리는 쉽게 구할 수 있다.
문제는 두 번째로 구해야 할 것(경우의 수)이다. 이걸 어떻게 구하지?
BFS의 원리를 생각하면서 그림을 그려보자.
2번에서 시작해서 BFS를 한번 돌리면 이런 식으로 갈 것이다.
BFS를 두 번 돌리면 목적지인 6에 하나가 도달하는 것을 볼 수 있다.
이때 최소 횟수가 2회인 것을 확인할 수 있다.
이제 나머지를 확인할 필요가 있을까? 필요가 없다.
왜냐하면 최소 횟수 2회를 넘어선 것이기 때문에 포함시키지 않아도 된다.
즉, 최소 시간일 때 목적지에 도달한 움직임만이
경우의 수에 포함된다는 것이다.
이를 이용하여 BFS를 구성하면 된다.
자세한 것은 문제 구현단계에서 보도록 하자.
3. 문제 구현 단계
<cpp />
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool visited[100001] = {false,};
int N, K;
int short_time;
int kind = 0;
int dx[] = {-1,1};
void bfs(int sx){
queue<pair<int,int>> q;
visited[sx] = true;
q.push({sx,0}); // 큐 안에 (좌표,시간)쌍으로 넣음
while(!q.empty()){
int x = q.front().first;
int time = q.front().second;
q.pop();
// 현재 좌표가 목적지 && 첫 방문일 때
if(x == K && !visited[x]){
short_time = time; // 최소시간으로 지정
kind++; // 방문횟수 +1
}
// 현재 좌표가 목적지 && 현재 시간이 최소 시간일 때
else if(x == K && time == short_time) kind++;
visited[x] = true; // 방문처리
for(int i = 0; i < 2; i++){
int nx = x + dx[i];
if(nx > 100000 || nx < 0 || visited[nx]) continue;
q.push({nx,time+1}); // 큐에 (다음좌표,현재시간+1)로 넣어줌
}
//마찬가지
if(2*x <= 100000 && !visited[2*x]) q.push({2*x,time+1});
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> K;
bfs(N);
cout << short_time << "\n" << kind;
}
집중해서 보아야 하는 것은 bfs함수 쪽이다.
큐를 만들어줄 때 pair를 사용하여 (좌표, 시간) 쌍으로 만들어줬다.
이렇게 함으로써 특정 좌표일 때의 시간을 알 수 있도록 만들어줬다.
bfs의 실행은 간단하다.
우선 항상 해당 좌표가 목적지인지 확인해 준다.
그리고 그 좌표가 목적지가 맞다면
그다음 체크해 주는 것은 첫 방문인가 아닌가이다.
만약 첫 방문이라면 그때의 시간을 최소시간으로 지정해 준다.
그리고 횟수+1을 해준다.
만약 첫 방문이 아니라면, 그때의 시간이 최소시간인지 확인한다.
최소시간이 맞다면 횟수+1을 해준다. 그 외에는 일반적인 BFS와 동일하다.
다른 것은 큐 안에 pair을 넣어줬기 때문에
(다음좌표, 현재시간+1) 이런 식으로 넣어줘야 한다는 것이다.
그렇게 bfs를 완료하면, 전역변수로 설정해 둔 short_time과 kind를 출력해 준다.
4. 시행착오
최소시간을 구하는 것은 쉬웠다.
하지만 문제는 경우의 수를 구하는 것이었다.
경우의 수를 구할 때 사용했던 방식은
백트래킹, 너비우선 탐색을 사용한 함수 하나 더 만들기.. 등등이 있는데
시간 초과, 메모리 초과 등 다양한 실패를 맞았다.
일단 내가 잘못했던 점은 너비 우선 탐색의 원리를 제대로 파악하지 않은 점.
만약 제대로 파악했다면 이 문제를 풀었을 것이다.
좀 더 공부하자.
토스아이디
toss.me