백준 1697 [C++]

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

1. 풀이방법.

 

- 0<N==K<100000 이 되는 모든 경우의 수를 탐색해야합니다.

 

- 움직일 수 있는 경우의 수는 3가지 X+1,X-1,2*N

 

- DFS로 모든 경우의수를 탐색할경우 +1,-1씩 이동하는경우 때문에 스택오버플로우가 발생할 것 이라 판단했습니다.

 

- 그래서 큐를 이용하여 BFS로 해결하였습니다. 

 

- 딱히 다른 조건도 없어 기본적인 문제였습니다.

 

 

 

 

2. 주의사항

 

- 문제 조건 해석 및 판단.

 

 

 

 

3.나의코드

#include<iostream>
#include<queue>
#include<vector>
#include<string>
using namespace std;

int N, K;
int resultsecond;
bool visit[100001]; //방문체크
queue<int> tmpq;


void bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			int thisvalue = tmpq.front();
			tmpq.pop();

			if (thisvalue == K) { //종료조건
				cout << resultsecond << "\n";  return;
			}

			if (thisvalue - 1 >= 0 && visit[thisvalue-1] == false) {
				visit[thisvalue - 1] = true;
				tmpq.push(thisvalue - 1);
			}
			if (thisvalue + 1 <= 100000 && visit[thisvalue+1] == false) {
				visit[thisvalue + 1] = true;
				tmpq.push(thisvalue + 1);
			}
			if (2 * thisvalue <= 100000 && visit[2*thisvalue] == false) {
				visit[2 * thisvalue] = true;
				tmpq.push(2 * thisvalue);
			}
		}
		resultsecond++;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	tmpq.push(N);
	visit[N] = true;
	bfs();

	return 0;
}