[백준][bfs] 13913 숨바꼭질4 c++ 구현

목차

 

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

문제

참고하면 도움될 만한 글

https://be-senior-developer.tistory.com/118

[백준][bfs] 12851 숨바꼭질2 c++구현

 

잘못된 접근 방향

아래코드와 같이 각 분기점마다 그 전 방문한 곳을 추가해주니 당연히도 메모리 초과가 났다..

그래서 하나의 방법만 탐색하는 식으로 접근해야 한다.

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

using namespace std;
int visit[100001] = { 0 };

int N, K;
//메모리 초과 이유
vector<int> cnt[100001];
int methods = 0;
int sec = 0;


void bfs() {
	queue<int> q;
	q.push(N);
	visit[N] = 1;
	cnt[N].push_back(N);
	while (!q.empty()) {
		int t = q.front();
		q.pop();

		if (t == K)
		{
			return;
		}
		for (int next : {t * 2, t - 1, t + 1}) {
			if (next < 0 || next > 100000)
				continue;
			if (!visit[next]) {
				q.push(next);
				visit[next] += visit[t] + 1;
				cnt[next].push_back(next);
				for (auto i : cnt[t])
					cnt[next].push_back(i);
			}
		
		}

	}
}


int main() {

	cin >> N >> K;
	bfs();
	cout << visit[K] - 1 << "\n";
	reverse(cnt[K].begin(), cnt[K].end());
	for (auto i : cnt[K])
		cout << i << " ";

}
/*
5 100000
*/

 

문제 접근 아이디어

다시 돌아가는 곳을 탐색할 수 있도록 prev배열을 통해 현 경로가 그 전 경로를 저장하도록 해야한다.

 

코드 구현

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

using namespace std;
int visit[100001] = { 0 };

//문제 방향성의 핵심
int Prev[100001] = { 0 };
int N, K;

vector<int> ans;
int sec = 0;


void bfs() {
	queue<int> q;
	q.push(N);
	visit[N] = 1;

	while (!q.empty()) {
		int t = q.front();
		q.pop();

		if (t == K)
		{
			return;
		}
		for (int next : {t * 2, t - 1, t + 1}) {
			if (next < 0 || next > 100000)
				continue;
			if (!visit[next]) {
				q.push(next);
				visit[next] += visit[t] + 1;
                //현 경로가 그 전 경로를 저장하게 한다.
				Prev[next] = t;
			}
		
		}

	}
}


int main() {

	cin >> N >> K;
	bfs();
	cout << visit[K] - 1 << "\n";
    
	for (int i = K; i != N; i = Prev[i]) {
		ans.push_back(i);
	}
	ans.push_back(N);  //시작점 추가
    //돌아가면서 저장한 배열이므로 다시 거꾸로 만들어 준다.
	reverse(ans.begin(), ans.end());
	for (auto i : ans)
		cout << i << " ";

}
/*
5 100000
*/