백준 17071번 숨바꼭질 5(C++)

문제

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

17071번: 숨바꼭질 5

정답 코드

/*
수빈이 위치 : N
동생 위치 : K
수빈 이동 : +-1, *2
동생 이동 : 1, 1+2, 1+2+3, 1+2+3+4 ...

동생을 처음 만나는 시간 : time
0 <= 위치 <= 500000

동생 위치 500000 넘으면 -1, 못찾는 경우 -1
시간 제한 : 0.25초 -> 25,000,000
동생[지난시간] = 위치
- 방문에 대한 가지치기를 잘 모르겠다.
- 한번 방문했으면, 또 방문하는 일이 없는걸까?
1 2 가 있다고 치자.
1->2->4->8
2->3->5->8
답 : 3

5 17 
5->10->20
17->18->20
답 : 2

17 5
17->16->15->16->15
5-> 6 ->8 ->11->15
//이런 경우도 있기 때문에 버릴 수는 없다.

홀수와 짝수를 이용해보자.
한칸 이동할 때는 짝->홀, 홀->짝
2배할 때는 짝->짝, 홀->짝
동생 위치는 홀(+1)->홀(1+2)->짝(3+3)->짝(6+4)->홀(10+5)->홀(15+6)->짝(21+7)->짝(28+8)->홀(36+9)->홀(45+10)->짝(55+11)->짝(66+12)
현재 같은 위치를 반복하는게, 저런 경우 하는건데, 이건 일정 시간 이후에 즉 짝수배의 시간이후, 이곳을 방문한다면? 그 경우를 도착으로 처리해준다면 vis처리를 
일반 bfs처럼 하면 괜찮지 않을까? 

반례 : 21 70
21->42->41->40->80
70->71->73->76->80->85->91

반례 : 18 66
18->36->72
66->67->69->72->76->81->87

반례 : 7 37
7-> 6-> 12->13->26->52
37->38->40->43->47->52
*/
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define TIME first
#define POS second
using namespace std;
int bro[500001];
bool vis[500001][2];
int N,K;
int mini = 500000000;
int main(){
	cin >> N >> K;
	int i =1;
	int pos = K;
	memset(bro,-1,sizeof(bro));
	while (pos <=500000){
		bro[pos] = i-1;
		pos+= i;
		i++;
	}
	queue<pair<int,int>> Q;
	Q.push({0,N});
	vis[N][0] = true;
	while (!Q.empty()){
		auto q = Q.front();
		Q.pop();
		if (bro[q.POS] != -1 &&  bro[q.POS] >= q.TIME && (bro[q.POS]-q.TIME)%2 == 0)
			mini = min(bro[q.POS],mini);
		if (q.POS > 0 && !vis[q.POS-1][(q.TIME+1)%2]){
			Q.push({q.TIME+1,q.POS-1});
			vis[q.POS-1][(q.TIME+1)%2] = true;
		}
		if (q.POS < 500000 && !vis[q.POS+1][(q.TIME+1)%2]){
			Q.push({q.TIME+1, q.POS+1});
			vis[q.POS+1][(q.TIME+1)%2] = true;
		}
		if (q.POS*2 <=500000&& !vis[q.POS*2][(q.TIME+1)%2]){
			Q.push({q.TIME+1, q.POS*2});
			vis[q.POS*2][(q.TIME+1)%2] = true;
		}

		
	}
	if (mini== 500000000)
		cout << -1 << "\\n";
	else 
		cout << mini << "\\n";
}

문제 풀이의 흐름

홀수와 짝수에 대한 아이디어만 얻으면 어렵지 않지만 그 아이디어가 쉽게 떠오르지는 않는 문제.

저는 이 문제를 우선 동생의 위치를 먼저 시간에 따라서 처리를 먼저 해줬습니다.

이 문제에서 핵심은 어떻게 하면 방문했던 곳을 또 방문하는 것을 잘 처리해줄 것인가 입니다.

무슨말이냐면, 일반적인 bfs의 경우는 한번 방문했던 곳을 방문하지 않습니다.

그러나 이 문제에서는 아래와 같은 케이스가 존재합니다

17 5
17->16->15->16->15
5-> 6 ->8 ->11->15

이 케이스 같은 경우 16을 이미 이전에 방문했는데 계속해서 방문 해야하는 경우가 생깁니다.

이렇게 되면 방문했던 곳을 vis로 처리하는 방식으로는 올바른 정답을 찾을 수 없습니다.

그렇다고 이 bfs를 사용할 때 vis처리를 안 해주면 무한대로 갔던 곳을 또 가기 때문에 가지치기가 전혀 안되서 시간초과 또는 메모리초과가 발생하게 될 것 입니다.

저는 이 문제의 최적의 경우들을 예시 입력을 보면서 어떤 흐름으로 그 답을 얻었는지 살펴보았습니다.

거기서 홀수와 짝수를 이용해서 풀 수 있지 않을까라는 생각을 하게 되었고, 한가지 규칙을 찾았습니다.

수빈이

• 수빈이가 이동할 때는 다음과 같은 규칙을 찾을 수 있습니다.
• 한칸 이동할 때는 짝->홀, 홀->짝
• 2배할 때는 짝->짝, 홀->짝

동생 위치

• 홀(+1)->홀(1+2)->짝(3+3)->짝(6+4)->홀(10+5)->홀(15+6)->짝(21+7)->짝(28+8)->홀(36+9)->홀(45+10)->짝(55+11)->짝(66+12)
• 현재 같은 위치를 반복하는게, 저런 경우 하는건데, 이건 일정 시간 이후에 즉 짝수배의 시간이후, 이곳을 방문한다면? 그 경우를 도착으로 처리해준다면 vis처리를 일반 bfs처럼 하면 괜찮지 않을까?

라는 생각을 하게 됩니다.

배열 bro에 동생이 해당 위치를 몇초에 도착하는지를 저장해줍니다.

만약 현재 수빈이가 있는 위치가 동생이 도착을 할 예정인 위치이고 둘 사이의 차이가 2의 배수라면 수빈이는 그 위치에서 앞뒤 앞뒤로 계속해서 이동하고 있으면 결국에 동생과 만날 수 있다는 것을 알 수 있습니다.

주의 할 점

처음에 여기까지 생각하고 코드를 구현했었습니다.

그러나, 여기까지만 생각하고 코드를 섣부르게 짜면 문제가 틀릴 수 있습니다.

• 위와 같은 조건문의 의미는 동생이 미래에 방문할 곳이면서, 남은 시간이 짝수인 경우입니다.
• if (bro[q.POS] != -1 && bro[q.POS] >= q.TIME && (bro[q.POS]-q.TIME)%2 == 0)

저는 이 조건문을 만나면 바로 종료하고 그곳까지 대기하는 시간만큼 처리를 했었습니다.

그러나, 실제로는 그 거리보다 빠르게 도착할 수 있는 경우가 있었습니다.

해당 경우를 처리해주기 위해서 bfs의 조건을 만났을 때 끝내는 대신 계속해서 돌리고 해당 시간을 최소값으로 저장하는 방식으로 처리했습니다.

반성 및 고찰

이 문제는 과거에 약 1년 정도 전에 실패해서 그냥 미뤄둔 문제였습니다.

이 문제를 답지를 보지 않고 아이디어를 생각해서 풀었다는 것이 많이 성장했다는 생각이 들어 뿌듯했습니다.

또한 섣부르게 테스트를 충분히 하지 않고 문제를 제출하는 방식은 좋지 않다는 것을 알았고, 문제를 풀 때 감이 아에 안 오는 경우 직접 예제를 컴퓨터처럼 돌려보다 보면 규칙이 보인다는 것을 알았습니다.

많은 걸 깨닫게 해준 문제여서 뜻 깊었습니다.