[BFS]02-백준 1697 숨바꼭질

**5백준1697번 숨바꼭질  **

 

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

1697번: 숨바꼭질

 

576번 대표적인

---

 

정답 코딩

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


int visit[100000] = { 0, };			//점 방문 여부 조사
int N, K;							//수빈과 동생의 위치
int sec = 0;						//수빈이가 동생을 찾을 수 있는 가장 빠른 시간
bool fff=false;					//찾았는지

int f_minus(int a){
	return a-1;
}

int f_plus(int a){
	return a+1;
}

int f_double(int a){
	return a*2;
}

int bfs(){

	queue<int> q;		//Queue 선언
	q.push(N);			//수빈 위치 q삽입
	visit[N]=1;			//방문 표시
	

	while(!q.empty()){
		
		sec++;	
		int qsize=q.size();
	
		for( int i=0; i<qsize; i++){
			int qvalue = q.front();			//q의 값 추출
			q.pop();
			/*	방문여부확인	*/
			if(f_minus(qvalue)==K) {fff=true; break;}			//동생 위치면
			if(visit[f_minus(qvalue)]==0) q.push(f_minus(qvalue));	//방문 안했으면
			if(f_plus(qvalue)==K) {fff=true; break;}
			if(visit[f_plus(qvalue)]==0) q.push(f_plus(qvalue));
			if(f_double(qvalue)==K) {fff=true; break;}
			if(visit[f_double(qvalue)]==0) q.push(f_double(qvalue));
		}

		if(fff)break;

	}
	return sec;
}

int main(){
	cout<<"위치 입력 : ";
	cin>>N>>K;			//수빈이와 동생 위치 입력
	cout<<bfs()<<"초 소요"<<endl;
	return 0;
}

 

---

 

5
4	6	10
3	8	7	12	9	11	20
2	16	14	13	24	18	22	19	21	40
1	15	17

q에 삽입되는 순서는 위와 같고 한줄씩 내려갈 때마다 sec가 증가된다.

아래 사진과 같이 수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다. (왜16이 아니라 18을 지나지?)

출력 콘솔