백준 17071 c++ "숨바꼭질 5" -PlusUltraCode-

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

 

 

[필자 사고]

이 문제는 BFS 탐색 알고리즘을 이용하여 풀 수 있다.

필자는 이 문제에서 방문지역을 어떻게 체크할지 고민했는데 다른 분들의 자료들을 찾아보니

visited[2][500001] 와 같은 형식으로 작성했따.

시간을 홀수 시간과 짝수 시간으로 방문지역을 체크했는데 

곰곰히 생각해보니 오른쪽 왼쪽 즉 왔다 갔다 할 수있다.

왔다 갔다 는 총 2초가 걸리므로 이미 그 지역을 방문한 흔적이 있다면 true로 해놓고

동생이 만약 그 지역에 방문하고 해당 시간이 홀수인지 짝수인지 맞다면 반복문을 끝내는 형식으로

코드를 작성하면 된다.

[코드 해설]

1. BFS를 이용한 탐색

• 이 코드는 BFS(Breadth-First Search)를 사용하여 문제를 해결합니다. BFS는 큐(queue)를 이용하여 상태를 탐색하며, 시간과 위치 정보를 함께 처리합니다.

2. 변수 및 주요 함수

• getMove 함수: 현재 위치에서 갈 수 있는 세 가지 경우를 반환합니다.
  • num - 1: 현재 위치에서 한 칸 뒤로 이동.
  • num + 1: 현재 위치에서 한 칸 앞으로 이동.
  • num * 2: 현재 위치에서 순간이동.
• isInside 함수: 주어진 위치가 유효한 범위(0 이상 MAX 이하) 안에 있는지 확인합니다.

3. BFS 구현

• 큐 초기화:
  • myQueue는 현재 위치와 시간을 저장합니다. 시작 위치(N)와 시간(0)을 큐에 추가합니다.
  • 방문 여부는 visited[2][MAX + 1] 배열로 관리하며, 시간에 따라 짝수와 홀수 레이어로 나누어 관리합니다.
• BFS 탐색 과정:
  1. 현재 상태 처리:
     • 큐에서 현재 위치(nowSubin)와 시간을 꺼냅니다.
     • 동생의 예상 위치(nextSibling)를 계산합니다. K + nowTime * (nowTime + 1) / 2로 계산되며, 이는 시간이 지남에 따라 동생의 위치가 증가함을 나타냅니다.
     • 동생의 위치가 범위를 벗어나면 -1을 출력하고 종료합니다.
     • 현재 위치가 동생 위치와 같거나 이미 방문한 위치라면 현재 시간을 출력하고 종료합니다.
  2. 다음 위치 탐색:
     • 가능한 세 가지 이동(getMove)을 시도하며, 이동한 위치가 유효하고 아직 방문하지 않은 경우 큐에 추가합니다.
     • 방문 여부를 기록하여 중복 탐색을 방지합니다.

4. 게임 시작

• Game_Start 함수:
  • 사용자로부터 초기 위치(N)와 동생의 위치(K)를 입력받습니다.
  • 방문 배열을 초기화한 후, BFS를 실행하여 탐색을 시작합니다.

5. 결과 출력

• BFS를 통해 탐색이 완료되면 동생을 만나는 데 걸리는 최소 시간을 출력하거나, 도달할 수 없을 경우 -1을 출력합니다.

[소스 코드]

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

#define MAX 500000
 
using namespace std;

int N, K;
bool visited[2][MAX + 1];

int getMove(int num, int idx) {
	if (idx == 0) {
		return num - 1;
	}
	else if (idx == 1) {
		return num + 1;
	}
	else {
		return num * 2;
	}
}
bool isInside(int num){
	if (num >= 0 && num <= MAX)return true;
	return false;
}

void BFS() {
	queue<pair<int, int>> myQueue;
	myQueue.push({ N,0 });
	visited[0][N] = true;

	while (!myQueue.empty()) {
		int nowSubin = myQueue.front().first;
		int nowTime = myQueue.front().second;
		myQueue.pop();
		
		int nextSibling = K + nowTime * (nowTime + 1) / 2;
		if (isInside(nextSibling) == false) {
			cout << -1;
			return;
		}

		if (nowSubin == nextSibling|| visited[nowTime%2][nextSibling]) {
			cout << nowTime << '\n';
			return;
		}

		
		for (int i = 0; i < 3; i++) {
			int nextSubin = getMove(nowSubin, i);
			if (isInside(nextSubin) == false)continue;
			if (visited[(nowTime + 1) % 2][nextSubin] == true)continue;

			myQueue.push({ nextSubin,nowTime + 1 });
			visited[(nowTime + 1) % 2][nextSubin] = true;
		}
	}

	cout << -1;
}

void Game_Start() {
	cin >> N >> K;

	memset(visited, false, sizeof(visited));
	BFS();

}

int main(void) {

	Game_Start();
}