백준 13913번 숨바꼭질4

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

13913번: 숨바꼭질 4

 

 

 

 

 

 

<접근방법>

탐색 문제입니다.

경로를 어떻게 저장할 것이냐가 문제입니다.

경로를 저장하기 위해 dfs를 사용해버리면 시간 초과가 날 것 입니다.

그래서 bfs를 사용하는 대신 경로 저장용 배열을 하나 만듭니다.

그리고 방문을 해가며 경로를 저장합니다.

이것이 가능한 이유는 가중치 순으로 방문하기 때문입니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;

struct point {
	int x, cnt;
};

int n, k;
int parent[100001];

vector<int> v;

void bfs() {
	queue<point> q;
	q.push({ n, 0});

	while (!q.empty()) {
		int x = q.front().x;
		int cnt = q.front().cnt;
		int nx;
		q.pop();

		if (x == k) {
			cout << cnt << '\n';
			v.push_back(k);

			int tmp = k;
			while (tmp != n) {
				v.push_back(parent[tmp]);
				tmp = parent[tmp];
			}

			for (int i = v.size() - 1; i >= 0; i--) {
				cout << v[i] << ' ';
			}
			puts("");
			return;
		}

		nx = x + 1;
		if (0 <= nx && nx <= 100000 && parent[nx] == -1) {
			q.push({ nx, cnt + 1});
			parent[nx] = x;
		}

		nx = x - 1;
		if (0 <= nx && nx <= 100000 && parent[nx] == -1) {
			q.push({ nx, cnt + 1 });
			parent[nx] = x;
		}

		nx = x * 2;
		if (0 <= nx && nx <= 100000 && parent[nx] == -1) {
			q.push({ nx, cnt + 1 });
			parent[nx] = x;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(parent, -1, sizeof(parent));

	cin >> n >> k;
	bfs();

	return 0;
}