[백준 BOJ][C++]13913번 숨바꼭질 4 풀이: BFS

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

13913번: 숨바꼭질 4

 

 이 문제는 BFS를 사용하여 해결할 수 있습니다. 

 

 먼저 BFS 탐색을 하면서 queue에 push할 node 구조체를 정의하겠습니다. 

 loc은 해당 노드의 위치, *parent는 부모 노드의 link입니다. 

 

 generated[MAX] 배열은 탐색 과정에서 생성된 노드를 체크할 배열입니다.

 generated[n] = true 라면 n 위치 노드는 이미 생성되었다는 것을 나타냅니다. 

 만약 이 배열을 사용하지 않는다면 어떻게 될까요?

 

 5의 자식 노드로는 4, 6, 10이 될 수 있습니다. 

 그 다음 레벨인 4, 6, 10의 자식 노드는 각각 (3, 5, 8), (5, 7, 12), (9, 11, 20) 이 되겠죠? 

 이때 탐색하면서 5를 또 생성하게 되면 4, 6, 10을 또 생성하게 되고 그 다음 자식들도 또 생성해서 탐색하지 않아도 될 경로도 탐색하게 되겠죠?

 때문에 노드를 생성할때마다 generated 배열의 해당 index 위치를 반드시 true로 set 해주어야 합니다. 

 

 BFS 탐색과정에서 노드의 위치(loc)이 k와 일치하다면 최단경로를 찾은 것이기 때문에 해당 노드부터 부모 노드에 접근하여 path 벡터에 loc을 저장한 뒤 탐색을 종료합니다. 

 

[풀이 과정]

1. 수빈이의 위치 n에 대하여 생성 표시(generated[n]=true)를 한다.

2. 수빈이의 위치 n에 대해 시작 노드(loc=n, parent=NULL)를 queue에 push한다.

3. queue의 원소를 pop하여 자식 노드를 생성한 뒤 queue에 push 한다. 

4. pop한 원소의 위치(loc)이 k와 일치할 때까지 2~3과정을 반복한다. 

5. 일치하다면 최단 경로에 도달한 것이므로, 부모 노드에 차례대로 접근하여 path 벡터에 위치 정보를 저장한 뒤 탐색을 종료한다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<cstdlib>
#include<algorithm>

using namespace std;

#define MAX 100001

typedef struct node {
	int loc; //위치
	node* parent; //부모 노드
}node;

int n, k;
bool generated[MAX] = { false, };
queue<node*> q;
vector<int> path; //경로

void bfs() {

	generated[n] = true;

	node* start = new node;
	start->loc = n;
	start->parent = NULL;

	q.push(start);

	while (!q.empty()) {
		node* temp = q.front();
		q.pop();

		if (temp->loc == k) {
			node* curr = temp;

			while (curr != NULL) {
				path.push_back(curr->loc);
				curr = curr->parent;
			}

			break;
		}

		for (int i = 0; i < 3; i++) {
			int tx; //자식 노드 위치
			if (i == 0)
				tx = temp->loc - 1;
			else if (i == 1)
				tx = temp->loc + 1;
			else
				tx = temp->loc * 2;

			if (tx < 0 || tx >= MAX)
				continue;
			if (generated[tx])
				continue;

			generated[tx] = true;
			
			node* child = new node;
			child->loc = tx;
			child->parent = temp;

			q.push(child);
		}
	}

}

int main(void) {

	cin >> n >> k;

	bfs();

	cout << path.size() - 1 << endl;

	while (!path.empty()) {
		cout << path.back() << " ";
		path.pop_back();
	}

	return 0;
}