[BOJ] 13913번 : 숨바꼭질 4

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first 
#define Y second 
int n, k;
pair<int,int> axis[200005]; 
int dx[2] = { 1,-1 };
queue<int> Q;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k; 
	fill(axis, axis + 200005, make_pair(-1, -1));
	axis[n] = { 0,n }; // cnt 와 전 index값 입력 
	Q.push(n); 
	bool isfind = false;
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 3; dir++) {
			int nx = 0;
			if (dir == 2) nx = cur + cur;
			else nx = cur + dx[dir];
			
			if (nx < 0 || nx > 200000) continue; 
			if (axis[nx].X >= 0) continue;
			axis[nx] = { axis[cur].X + 1, cur };
			Q.push(nx);
			if (nx == k) {
				isfind = true; 
				break;
			}
		}
		if (isfind) break;
	}
	vector<int> ans; 
	int idx = k;
	while (idx != n) {
		ans.push_back(idx); 
		idx = axis[idx].Y;
	}	
	ans.push_back(n); 
	reverse(ans.begin(), ans.end());
	 
	cout << axis[k].X << '\n';
	for (auto x : ans) cout << x << ' ';
}

bfs를 이용해 풀었다. 여기서 중요한 부분은 axis라는 배열에 전 index를 추적할 수 있도록 했다는 것이다. 따라서, bfs를 이용해 찾아온 경로를 역추적할 수 있다. 

 

3. solution 2 :

// Authored by : heheHwang
// Co-authored by : -
// http://boj.kr/fd3427431325431ea6a82e4938589c0d
#include <bits/stdc++.h>
using namespace std;

const int LMT = 100001;
int board[LMT + 2];
int prePos[LMT + 2];
int sis, bro;
queue<int> Q;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> sis >> bro;
  board[sis] = 1;
  prePos[sis] = sis;
  Q.push(sis);
  while (!board[bro]) {
    int v = Q.front(); Q.pop();
    for (int nv : { v + 1, v - 1, 2 * v }) {
      if (nv < 0 || LMT <= nv) continue;
      if (board[nv]) continue;
      board[nv] = board[v] + 1;
      prePos[nv] = v;
      Q.push(nv);
    }
  }
  cout << board[bro]-1 << '\n';
  deque<int> track = {bro};
  while (track.front() != sis)
    track.push_front(prePos[track.front()]);
  for (int p : track) cout << p << ' ';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/13913.cpp

basic-algo-lecture/0x09/solutions/13913.cpp at master · encrypted-def/basic-algo-lecture