백준 13913. 숨바꼭질 4

알고리즘 기초 문제 중 610 - BFS

숨바꼭질 4

1. 간단 설명

이전에 풀었던 숨바꼭질 문제에서

최단 경로를 출력하는 부분이 추가된 문제

2. 예시

• 수빈이는 5, 동생은 17에 있는 경우

5 -> 10 (*2) -> 9 (-1) -> 18 (*2) -> 17 로 이동하는 경우 4초만에 찾을 수 있음

또한

5 4 8 16 17도 4초만에 찾을 수 있다

둘 중 아무거나 출력해도 정답임

3. 알고리즘

BFS를 이용하여 최단 경로를 추적하면서

경로를 기록해두고, 동생을 찾았을 경우 이 경로를 출력하면 된다

1. N과 K를 입력받는다
2. BFS 시작
	2-1. {좌표 위치, 시간} 쌍을 이용하여 큐를 생성
	2-2. 시작 위치 방문 표시 및 경로에 기록, 큐에 초기 위치 넣기 
	2-3. 큐가 빌 때까지 다음 반복
		2-3-1. 큐의 맨 앞에서 노드 꺼내기
		2-3-2. 만약 좌표가 K라면, 동생을 찾은 것임
			- 현재까지 걸린 초와, 기록된 경로를 출력후 종료한다
		2-3-3. { -1, +1, *2} 중 하나를 선택하여 그 방향으로 이동해본다
		2-3-4. 만약 맵 밖이라면 이동 불가
		2-3-5. 만약 방문했던 곳이라면 건너 뛴다
		2-3-6. 위 조건들을 통과했다면, 방문 처리 후, 경로에 기록한뒤, 큐에 넣는다

필요 변수

수빈이와 동생의 좌표 int N, K (0 ≤ N, K ≤ 100,000)

주의사항

좌표는 0도 포함하므로, 방문 처리 배열을 사용할 때 주의해야한다

방문처리 배열과 경로 배열을 같이 사용해버리는 경우 0 4 와 같은 경우를 제대로 처리할 수 없는 문제가 발생한다

방문하지 않아서 0으로 표기한 것인지, 0으로부터 와서 0으로 표기한 것인지 구분이 불가능하기 때문

이를 제대로 처리하거나, 별도의 배열을 사용하는 것이 좋다

4. 소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 100001

using namespace std;

int N, K;
bool visited[MAX];
int path[MAX];

int main() {
	cin >> N >> K;
	
	queue< pair<int, int> > qu;
	qu.push({ N, 0 });
	visited[N] = true; // 시작 위치 지정
	path[N] = N;

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		if (now.first == K) {
			cout << now.second << '\n';
					
			// 경로 출력
			vector<int> result;
		
			while (path[K] != K) {
				result.push_back(K);
				K = path[K];
			}
			result.push_back(N);

			reverse(result.begin(), result.end());

			for (int e : result) {
				cout << e << " ";
			}cout << '\n';


			return 0;
		}

		int direct[3] = { -1, 1, now.first };

		for (int t = 0; t < 3; t++) {
			int next = now.first + direct[t]; 
			if (next < 0 || next >= MAX) continue; // 범위 초과
			if (visited[next] == true) continue; // 이미 한번 방문했던 곳

			visited[next] = true;
			path[next] = now.first; 
			qu.push({ next, now.second + 1 });
		}
	}

	return 0;
}