백준 12851 c++ "숨박꼭질2" -PlusUltraCode-

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

 

 

[필자 사고]

BFS 탐색을 이용하여 원하는 이동할 위치를 우선순위큐에 넣어 탐색을 진행하는 문제이다.

이 문제에서 조심해야 될점은 visited관련 방문처리이다.

경로가 다르면 같은 장소를 방문해도 문제가 되지 않는다.

즉 visited를 우선순위 큐에 넣을때 방문처리를 하는게 아니라

방문한 후에 그제서야 visitied 를 true 로 해줘야 된다.

 

아래는 코드해설이다.

 

priority_queue를 사용하여 출발 지점에서부터 목표 노드 K까지 최단 시간을 구하는 BFS 알고리즘을 설명한다. 여기서 최단 시간을 찾은 후, 최단 시간에 도달하는 경로의 개수를 구하는 방식이다.

1. 입력 처리 및 초기화: Input() 함수는 사용자로부터 시작 지점 N과 목표 지점 K를 입력받고, visited 배열을 초기화하여 방문 여부를 관리한다. 방문할 수 있는 최대 범위는 MAX_SIZE = 100,000이다.
2. 우선순위 큐의 정의: priority_queue를 사용하여 BFS를 수행한다. 여기서는 짧은 시간이 우선적으로 처리되도록 우선순위를 설정하는데, cmp 구조체는 두 노드 중 시간이 적은 노드를 우선 처리하는 비교 연산을 담당한다.
3. 탐색 범위 체크: isInside() 함수는 이동할 노드가 범위 내(0 <= num <= 100,000)에 있는지 확인한다. 이 범위를 벗어나면 탐색하지 않는다.
4. BFS 알고리즘 구현: BFS() 함수는 우선순위 큐를 사용하여 BFS를 진행한다. 탐색은 시작점 N에서 시작하며, 목표 지점 K에 도달할 때까지 경로를 탐색한다. BFS는 다음과 같은 과정을 따른다:
   • 우선순위 큐에 현재 위치와 소요 시간을 넣고, 방문 여부를 기록한다.
   • 큐에서 현재 노드를 꺼내어 처리하는데, 목표 지점 K에 도달했을 때 그 시간이 최단 시간(resultNowCount)보다 크면 더 이상 진행하지 않는다.
   • 목표 지점 K에 처음 도달하면 해당 시간을 기록하고, 그 이후로도 동일한 시간에 도달할 경우 경로의 개수를 세는 방식이다.
5. 이동 가능한 경우 탐색: 현재 위치에서 1칸 앞으로, 1칸 뒤로, 그리고 2배로 이동하는 3가지 경우를 고려하며, 각각이 범위 내에 있고 아직 방문하지 않았을 때 큐에 추가한다.

 

 

[소스 코드]

#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 MAX_SIZE = 100000;
int N, K;
int resultCount = 0;
int resultNowCount = -1;
priority_queue<Node, vector<Node>, cmp > pq;
vector<bool> visited;

void Input() {
	cin >> N >> K;
	visited.resize(MAX_SIZE+1, false);
}

bool isInside(int num) {
	if (num <= MAX_SIZE&&num>=0)return true;
	return false;
}
void BFS(int startIdx) {
	pq.push({ startIdx,0 });
	visited[startIdx] = true;
	
	while (!pq.empty()) {
		int nowIdx = pq.top().first;
		int nowCount = pq.top().second;
	
		visited[nowIdx] = true;

		pq.pop();
		
		if (resultNowCount != -1 && resultNowCount < nowCount)return;

		if (nowIdx == K) {
			if (resultNowCount == -1) {
				resultNowCount = nowCount;
				resultCount++;
			}
			else if (resultNowCount == nowCount) {
				resultCount++;
			}
		}

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

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

		
	}
}

void GameStart() {
	BFS(N);
	cout << resultNowCount << '\n';
	cout << resultCount;
}

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