백준 13913 c++ "숨바꼭질 4" -PlusUltraCode-

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

 

 

 

[필자 사고]

bfs 탐색을 활용하여 현재위치에서 상대방의 위치까지의 경로를 찾아야 되는 문제이다.

현재위치에서 상대방까지 가는 방식은 숨바꼭질 1,2,3 에서 쉽게 알 수 있따.

다만 경로를 저장하는건 다른 방식앋.

 

무식하게 매번 배열을 만들어서 경로를 저장하고 큐에 저장하게 되면 메모리와 시간초과가 나게 된다.

 

새로 배운 방식은 vistied배열에 값에 자신의 이전 노드를 저장하는 방식이다.

vistied[next] = nowIdx; 방식으로 저장하게 되면 어떤 경로로 진행했는지 알 수 있게 된다.

 

다음은 아래의 코드 해설이다.

 

1. 입력 처리 및 초기화

먼저, 사용자로부터 출발점 N과 목표점 K를 입력받습니다. 그 후, 방문 여부를 저장하는 배열을 초기화합니다. 이 배열은 BFS 탐색 중에 방문한 노드를 기록하고, 해당 노드에 도달했을 때의 이전 노드를 저장하는 방식으로 경로를 추적합니다.

2. BFS 알고리즘

BFS는 출발점에서부터 목표점까지의 최단 경로를 찾는 데 적합한 알고리즘입니다. 여기서는 우선순위 큐를 사용해 BFS를 수행합니다. 큐에는 현재 위치와 그 위치까지 도달하는 데 걸린 시간을 저장합니다.

탐색 과정은 다음과 같습니다:

• 출발점 N을 큐에 넣고 탐색을 시작합니다.
• 현재 노드에서 이동할 수 있는 3가지 경우(한 칸 앞으로, 한 칸 뒤로, 두 배로 이동)를 고려하여, 각각의 경우에 대해 유효한 범위 내에 있고 아직 방문하지 않은 노드라면 큐에 추가합니다.
• 각 노드가 방문될 때마다, 그 노드에 도달한 이전 노드를 기록하여 경로를 추적할 수 있도록 합니다.

3. 목표 지점 도달 시 경로 추적

BFS 탐색 중 목표점 K에 도달하면, 그때까지의 소요 시간을 출력합니다. 이후, visited 배열을 사용하여 목표점에서 출발점으로 거슬러 올라가면서 경로를 추적합니다. 이 과정에서 각 노드가 어디서 왔는지를 역으로 찾아 경로를 복원한 후, 그 경로를 순서대로 출력합니다.

4. 결과 출력

최종적으로, 목표점에 도달할 수 있는 가장 짧은 시간과 그 경로를 출력합니다. 경로는 목표점에서 출발점까지의 노드를 차례대로 출력하며, 경로 추적이 완료되면 탐색이 종료됩니다.

 

 

[소스 코드]

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

using namespace std;

typedef pair<int, int> Node;

struct cmp {
	bool operator()(Node a, Node b) {
		return a.second > b.second;
	}
};

int N, K;
const int MAX_SIZE = 100000;
vector<int> visited;
priority_queue<Node, vector<Node>, cmp> pq;
int resultNowCount = -1;

void Input() {
	cin >> N >> K;
	visited.resize(MAX_SIZE + 1, -1);
}
bool isInside(int num) {
	if (num >= 0 && num <= MAX_SIZE)return true;
	return false;
}


void BFS(int startIdx) {
	pq.push({ startIdx,0 });
	visited[startIdx] = startIdx;
	while (!pq.empty()) {
		int nowIdx = pq.top().first;
		int nowCount = pq.top().second;
		
		pq.pop();
		
		if (nowIdx == K) {
			cout << nowCount << '\n';

			vector<int> path;
			for (int i = K; i != N; i = visited[i]) {
				path.push_back(i);
			}
			path.push_back(N);

			for (int i = path.size() - 1; i >= 0; i--) {
				cout << path[i] << " ";
			}
			cout << '\n';
			return;
		}

		int plus = nowIdx + 1;
		int minus = nowIdx - 1;
		int multi = nowIdx * 2;

		if (isInside(plus) && visited[plus] == -1) {
			pq.push({ plus,nowCount + 1 });
			visited[plus] = nowIdx;
		}
		if (isInside(minus) && visited[minus] == -1) {
			pq.push({ minus,nowCount + 1 });
			visited[minus] = nowIdx;
		}
		if (isInside(multi) && visited[multi] == -1) {
			pq.push({ multi,nowCount + 1 });
			visited[multi] = nowIdx;
		}

	}
}

void GameStart() {

	BFS(N);
}

int main(void) {
	Input();
	GameStart();
}