[C++]숨바꼭질 - 백준1697

문제

• 숨바꼭질(백준1697)

풀이

문제 해석을 하자면,

• 수빈이와 동생의 위치가 주어지면, 수빈이가 몇초를 이동해야 동생의 위치를 찾을 수 있는지 구하는 문제이다.
• 복잡도가 클거 같지는 않다는 생각에 “브루트포스”로 구현해보겠다.

풀이

• BFS를 상황에 맞게 진행한다.
  • 예로 수빈이가 동생보다 위치가 크다면 X-1, X+1, X*2 동작을 진행하자.
  • 이때, 중요한것은 이렇게 변화한 위치들도 “큐”에 넣어서 접근해봐야 하기 때문에
  • inArr을 Vector 배열로 선언해서 변화 위치들을 전부 기록후 “큐”에 inArr의 index값을 기록해서 사용한다.
• 모든 경우를 따진 후 가장 최소의 시간을 구한다.
  • 이때, 시간을 따로 배열을 선언해서 기록해둔다.
  • BFS 특성상 최소시간을 구하기 위해선 최초로 접근한 시간만 기록하면 된다.

코드

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

int outArr[100005]; // time 기록
bool visited[100005];
vector<int> inArr[100005];

int N, K; // 수빈, 동생 위치
int i, j, k;

void bfs();

int main() {
	// input
	cin >> N >> K;

	// run
	if (N != K) { // 혹시 처음부터 위치 동일한 경우 예외
		visited[N] = true;
		inArr[N].push_back(N - 1);
		inArr[N].push_back(N + 1);
		inArr[N].push_back(N * 2);
		bfs();
	}
	
	// output
	cout << outArr[K];

	return 0;
}

void bfs() {
	queue<int> qu;
	int cx = 0;
	int px = 0;

	qu.push(N); // 시작점 : 수빈 위치

	while (!qu.empty()) {
		cx = qu.front();
		qu.pop();
		//cout << cx << ' ';

		for (auto nx : inArr[cx]) { // inArr[cx] 에 존재하는 값 전부 조회
			if (nx < 0 || nx>100000) continue; // 범위 내 체크
			if (outArr[nx] != 0) continue; // 값이 이미 있는경우 할 필요 없음.

			if (!visited[nx]) {
				visited[nx] = true;
				inArr[nx].push_back(nx - 1);
				inArr[nx].push_back(nx + 1);
				inArr[nx].push_back(nx * 2);
			}

			outArr[nx] = outArr[cx] + 1; // 1초 경과
			qu.push(nx);

			// 동생을 찾은경우? 종료
			if (nx == K) return;
		}
	}
}

느낀점

생략