[BOJ] 1697번 : 숨바꼭질

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h> 
using namespace std; 

int board[200005]; 
int pos1, pos2; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	cin >> pos1 >> pos2; 
	fill(board, board + 200005, -1); 
	queue<int> Q; 
	if (pos1 == pos2) {
		cout << 0 << '\n'; // 시작 위치와 목표 위치가 같으면 0초
		return 0;
	}
	board[pos1] = 0;
	Q.push( pos1 ); 
	while (!Q.empty()) {
		int current = Q.front(); Q.pop();
		int dx1 = current - 1;
		int dx2 = current + 1; 
		int dx3 = current * 2; 
		if (dx1 < 200005 && dx1 >= 0 && board[dx1] == -1) {
			board[dx1] = board[current] + 1; 
			Q.push(dx1);
			if (dx1 == pos2) {
				cout << board[dx1] << '\n'; 
				return 0;
			}
		}
		if (dx2 < 200005 && dx2 >= 0 && board[dx2] == -1) {
			board[dx2] = board[current] + 1;
			Q.push(dx2);
			if (dx2 == pos2) {
				cout << board[dx2] << '\n';
				return 0;
			}
		}
		if (dx3 < 200005 && dx3 >= 0 && board[dx3] == -1) {
			board[dx3] = board[current] + 1;
			Q.push(dx3);
			if (dx3 == pos2) {
				cout << board[dx3] << '\n';
				return 0;
			}
		}
	}

	return 0;
}

일차원배열에서의 bfs이용 

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/ba53d62b7651443cbf7b2028c28ce197
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dist[100002];
int n,k;
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  fill(dist, dist+100001,-1);
  dist[n] = 0;
  queue<int> Q;
  Q.push(n);
  while(dist[k] == -1){
    int cur = Q.front(); Q.pop();
    for(int nxt : {cur-1, cur+1, 2*cur}){
      if(nxt < 0 || nxt > 100000) continue;
      if(dist[nxt] != -1) continue;
      dist[nxt] = dist[cur]+1;
      Q.push(nxt);
    }        
  }
  cout << dist[k];
}

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

for (int nxt : {cur -1 , cur + 1, cur * 2 } ) 이 부분이 신기했다.