[ 백준 12851 ] 숨바꼭질 2 (C++)

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

12851번: 숨바꼭질 2

고민하다가 못 풀어서 정답을 봤다. 근데 대부분의 코드가 비슷했다. 다들 누군가의 코드를 참고했나...? 약간 발상의 전환이 필요한 문제다. 일반 bfs와 달랐던 점은 두 개였다.

 

1. 큐에 push 할 때 현재 위치 외에 time이라는 변수 추가
2. 방문처리의 위치

 

나는 기존에 bfs 문제를 풀 때 방문처리를 범위 조건문 안에서 해줬다. 그러니깐 새로운 원소를 큐에 push 하기 직전에 방문처리를 했줬다. 그런데 이러면 '재방문'이라는 경우의 수를 놓치게 된다.

 

무슨 말이냐 하면... 1에서 2로 갈때 1+1도 되고 1*2도 된다. 두 가지 경우의 수다. 그런데 만약에 조건문 안에서 방문처리를 해주면 둘 중 하나는 큐에 들어가지 못한다. 정답 코드를 보면 세 개의 if문에서 각각 큐에 원소가 삽입되는데, 조건문 안에서 방문처리를 해주면 하나가 방문처리 돼서 나머지 하나의 !map 조건이 거짓이 돼버린다.

 

 

목적지를 재방문 하는 경우는 cnt 변수를 활용하면 경우의 수를 고려해줄 수 있다. cnt의 값이 0이면 목적지에 처음 도달했다는 뜻이므로 이 때의 time이 정답이 된다. 만약에 다음 time의 값이 정답과 일치하고, cnt의 값이 0이 아니면 재방문 했다는 뜻이므로 cnt를 1 더해준다. 

 

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

int map[100001];
int from, to, loc, time, ans;

int main() {
	cin >> from >> to;
	
	queue<pair<int, int>> q;
	q.push({from, 0});
	int cnt = 0;

	while (!q.empty()) {
		loc = q.front().first;
		time = q.front().second;
		q.pop();

		map[loc] = 1;

		// 목적지 재방문
		if (cnt > 0 && loc == to && ans == time) {
			cnt++;
		}

		// 목적지 첫 방문
		if (cnt == 0 && loc == to) {
			ans = time;
			cnt++;
		}

		if (loc + 1 <= 100000 && !map[loc + 1])
			q.push({ loc + 1, time + 1 });

		if (loc - 1 >= 0 && !map[loc - 1])
			q.push({ loc - 1, time + 1 });

		if (loc * 2 <= 100000 && !map[loc * 2])
			q.push({ loc * 2, time + 1 });
	}

	cout << ans << endl << cnt << endl;

	return 0;
}