BOJ 1697 : 숨바꼭질

[문제]

- 수빈이 위치 N, 동생 위치 K로 나타낼 수 있다. (0<=N<=100,000)

- 수빈이는 1초 후 걷기 혹은 순간이동으로 X에서 X-1, X+1, 2*X로 이동한다.

- N과 K가 주어졌을 때 수빈이가 동생에게 도달할 수 있는 가장 빠른 시간

= 결국 N에서 K까지 연결된 노드를 따라 이동할 때 최단 거리 => BFS로 풀자

 

* 입력 : N, K 

* 출력 : N부터 K까지 최단 거리 (가장 빠른 시간)

 

[풀이]

- 현재 위치를 node라고 했을 때 next가 될 수 있는 것은

=> node+1, node-1, 2*node

- 위의 3개 노드를 bfs방식으로 탐색한다.

- node 또는 next가 map의 범위를 벗어나거나 node가 k, 즉 동생 위치에 도달했을 경우 continue

* 런타임에러 발생 원인 : node 예외처리만 해주고 next에 대해서 처리를 안해줘서 발생

 

[코드]

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

const int MAX = 100001;
int n, k;
vector<int> map[MAX];
bool vis[MAX]; //방문 여부 확인
int dist[MAX]; //거리(초) 저장

void bfs(int start) {
	//초기화부분
	queue<int> q;
	memset(vis, false, sizeof(vis));
	memset(dist, 0, sizeof(dist));
	vis[start] = true;
	q.push(start);
	dist[start] = 0;
	//bfs시작
	while (!q.empty()) {
		int node = q.front();
		q.pop();

		int next;
		//예외처리
		if (node == k)break;
		if (node >= MAX||node<0)break;
		for (int i = 0; i < 3; i++) {
			//세가지 경우 나눠서 next결정
			if (i == 0) next = node + 1;
			if (i == 1) next = node - 1;
			if (i == 2) next = 2 * node;
			// next또한 map의 범위 밖에 나가면 안되므로 처리
			if (next >= MAX || next < 0) continue;
			
			if (vis[next] == false) {
				vis[next] = true;
				q.push(next);
				dist[next] = dist[node] + 1;
			}
		}
	}
}

int main() {
	cin >> n >> k;
	bfs(n);
	cout << dist[k] << "\n";
	return 0;
}