[C++] 백준 17071 : 숨바꼭질 5

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

17071번: 숨바꼭질 5

 

 

문제에서 나는 -1, +1, *2 와 같이 위치를 이동할 수 있는데,

*2의 경우는 일단 제쳐두고 +-1만 생각하면

t초에 X의 위치에 있었다면 t+2n 초에도 X의 위치로 갈 수 있다.

*2가 있어서 헷갈리는데, *2가 있다고 해서 위의 말이 거짓이 되는 건 아니다.

*2로부터 추가적인 규칙이 안 생길 뿐이지..

 

그래서 일반적인 BFS와는 다르게,

"t초에 X의 위치에 있었다면 t+2n 초에도 X의 위치로 갈 수 있다." 라는 걸 이용해야 한다.

 

애초에 BFS를 이용하는 이유가 이런 문제에서는 움직일수록 목표에 무조건 가까워 지는 것이 아니므로

중복제거가 목적인데,

이 문제는 단순히 나의 위치를 가지고 중복을 제거할 수 없다

(답에 영향을 주는게 나의 위치 말고 동생의 위치도 있으므로)

 

그렇다고 중복을 제거 안 하면 당연히 시간초과가 나고,

그래서 번뜩이는 아이디어(ㅋㅋ ㅜ)로 중복이 되는 케이스를 찾는 게 관건인데,

그 케이스가 "t초에 X의 위치에 있었다면 t+2n 초에도 X의 위치로 갈 수 있다." 라는 규칙에서 나온다.

 

암튼 아이디어를 도출하는게 어려운 문제지만

어떻게든 문제 접근 방법을 잘 생각해 본다면

3^(무한대)의 경우의 수 -> 중복 제거가 필요 -> 위치만으로는 중복 제거 불가능 -> 어떻게?

라고 생각해 보면... 접근할 수도 있지 않을까

 

근데 이게 저걸 깨닫고 나서도 조금 풀기가 까다롭다

조심해야 될 부분이 몇 개 있는데,

이 예제에서, 내가 17 -> 16 -> 15 -> 14 -> 15로 움직이면 4초 안에 동생과 만날 수 있다 (다른 움직임도 가능)

보면 내가 2초에 15를 들리고 또 4초에 15를 들린다

따라서 2초에 15를 들렀으므로 2초 + 2*1초인 4초에는 들리지 않는 것이 맞지만,

그렇게 해주면 답을 못 맞힌다 ㅋㅋ

 

애초에 "t초에 X의 위치에 있었다면 t+2n초에도 X의 위치로 갈 수 있다"라는 규칙에서,

t초에 X에 갔으면 t+2n 초에는 안 가야지~ 가 맞긴 하지만

그건 최적화만 생각한 거고 문제 푸는 건 하나도 생각 안 한 거다..

visit을 다음과 같이 채워나가면,

현재 나의 위치 cur가 동생의 위치 brother랑 같은지 봐줄 뿐만 아니라

이전에 내가 갔었던 위치가 기록된 visit에서,

혹시 brother도 왔었는지 확인해 주는 것이 필요하다 이게 저 규칙에서 찾아낼 수 있는 핵심적인 부분이다.

 

나의 위치 cur는 줄었다 늘었다 중복이 될 수도 있지만

동생의 위치 brother는 늘어나기만 하고 중복이 절대 생기지 않기 때문에

이 문제는 내 위치를 기준으로 둔다기보다는 동생의 위치를 기준으로 두면 생각하기가 좀 더 편하다

 

암튼 그래서 

while (!q.empty()) {
    int cur = q.front().first;
    int cnt = q.front().second;
    q.pop();
    int brother = K + (cnt * (cnt + 1) / 2);
    if (cur == brother) return cnt;
    if (cnt & 1 && hol_visit[brother]) return cnt;
    if (!(cnt & 1) && jjak_visit[brother]) return cnt;
	...
}

위와 같이 아래 cur==brother인지 확인하고

brother위치를 전에 내가 왔었는지 확인하는 게 반드시 필요하다

 

이것 말고도 조심해야 될 부분이 두 개 더 있는데..

 

첫 번째는

while (!q.empty()) {
    int cur = q.front().first;
    int cnt = q.front().second;
    q.pop();
    int brother = K + (cnt * (cnt + 1) / 2);
    if (brother > 500000) return -1;//이거 조심
    //50만 넘어서도 만나는걸 체크함..
    if (cur == brother) {
        return cnt;
    }
    if (cnt & 1 && hol_visit[brother]) return cnt;
    if (!(cnt & 1) && jjak_visit[brother]) return cnt;
    ...
}

brother가 50만을 넘는 경우를 처리 안 해주면,

cur 자체는 50만을 넘는 얘가 절대 안 들어오기 때문에

if(cur==brother) return cnt; 에 걸리는 건 아니지만,

그 밑에 return문 두 개에 걸리는 것 같다 (visit을 50만까지만 0으로 초기화해 줬으므로)

 

그리고 애초에 brother가 50만을 넘으면 볼 필요가 없으므로(brother는 커지기만 함)

최적화를 위해서라도 return -1; 해주는 게 좋다

 

두 번째는

while (!q.empty()) {
    ...
    int nxt = cur * 2;//next니까 홀수일때 짝수 visit 체크해주는거 조심
    if (nxt <= 500000 && (cnt & 1 ? !jjak_visit[nxt] : !hol_visit[nxt])) {
        cnt & 1 ? jjak_visit[nxt] = true : hol_visit[nxt] = true;
        q.push({ nxt , cnt + 1 });
    }
    nxt = cur + 1;
    if (nxt <= 500000 && (cnt & 1 ? !jjak_visit[nxt] : !hol_visit[nxt])) {
        cnt & 1 ? jjak_visit[nxt] = true : hol_visit[nxt] = true;
        q.push({ nxt , cnt + 1 });
    }
    nxt = cur - 1;
    if (nxt >= 0 && (cnt & 1 ? !jjak_visit[nxt] : !hol_visit[nxt])) {
        cnt & 1 ? jjak_visit[nxt] = true : hol_visit[nxt] = true;
        q.push({ nxt , cnt + 1 });
    }
}

cnt가 홀수일 때 hol_visit에 체크해 주는 게 아니라는 거다

저기서 visit 체크해 주는 건 cnt + 1 상태인 next를 체크해 주는 것이므로

cnt가 홀수면 짝수 visit 체크 / cnt가 짝수면 홀수 visit 체크

이렇게 해주면 된다

 

내가 말한 조심 해야 될 부분들이

반례로 여기에 다 있다

https://www.acmicpc.net/board/view/99122

글 읽기 - 최적화 쓰레기같이 한 사람들을 위한 반례 투척

ㅋㅋ 제목이 너무 아파요~

내 기억엔 brother 50만 넘는 거 체크 안 해주면 첫 번째 케이스에서 문제가 생겼던 것 같고,

next 짝홀 헷갈리면 마지막 케이스에서 문제가 생겼던 것 같다

 

전체코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int N, K;
bool hol_visit[500001];
bool jjak_visit[500001];

int bfs() {
	queue<pair<int, int>> q;
	q.push({ N, 0 });
	jjak_visit[N] = true;

	while (!q.empty()) {
		int cur = q.front().first;
		int cnt = q.front().second;
		q.pop();
		int brother = K + (cnt * (cnt + 1) / 2);
		if (brother > 500000) return -1;//이거 조심
		//50만 넘어서도 만나는걸 체크함..
		if (cur == brother) {
			return cnt;
		}
		//이것도 조심 ( 핵심임 )
		if (cnt & 1 && hol_visit[brother]) return cnt;
		if (!(cnt & 1) && jjak_visit[brother]) return cnt;

		int nxt = cur * 2;//next니까 홀수일때 짝수 visit 체크해주는거 조심
		if (nxt <= 500000 && (cnt & 1 ? !jjak_visit[nxt] : !hol_visit[nxt])) {
			cnt & 1 ? jjak_visit[nxt] = true : hol_visit[nxt] = true;
			q.push({ nxt , cnt + 1 });
		}
		nxt = cur + 1;
		if (nxt <= 500000 && (cnt & 1 ? !jjak_visit[nxt] : !hol_visit[nxt])) {
			cnt & 1 ? jjak_visit[nxt] = true : hol_visit[nxt] = true;
			q.push({ nxt , cnt + 1 });
		}
		nxt = cur - 1;
		if (nxt >= 0 && (cnt & 1 ? !jjak_visit[nxt] : !hol_visit[nxt])) {
			cnt & 1 ? jjak_visit[nxt] = true : hol_visit[nxt] = true;
			q.push({ nxt , cnt + 1 });
		}
	}
	return -1;
}

int main() {
	scanf("%d%d", &N, &K);
	printf("%d", bfs());
}