[백준] 12851번 : 숨바꼭질 2 [C/C++]

#문제

12851번: 숨바꼭질 2

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

12851번: 숨바꼭질 2

 

---

#접근방법

너비 우선 탐색(bfs) 알고리즘을 사용하면 풀 수 있다.

반응형

---

#풀이

#include <stdio.h>
#include <queue>
using namespace std;

int visit[100005];

int main(){
	int n,k;
	int ans1 = 987654321;
	int	ans2 = 0;
	queue<pair<int,int> > q;
	
	scanf("%d %d",&n,&k);

	q.push(make_pair(n,0));
	
	while(!q.empty()){
		int x = q.front().first;
		int num = q.front().second;
		q.pop();
		
		visit[x] = 1;
		
		if(ans1<num) break;
		
		if(x==k){
			ans1 = num;
			ans2++;
			continue;
		}
		
		if(x-1>=0 && !visit[x-1])
			q.push(make_pair(x-1,num+1));
		if(x+1<=100000 && !visit[x+1])
			q.push(make_pair(x+1,num+1));
		if(x*2<=100000 && !visit[x*2])
			q.push(make_pair(x*2,num+1));
	}
	
	printf("%d\n%d",ans1,ans2);
	
	return 0;
}

 

너비 우선 탐색을 사용하기 위해 queue라는 자료구조를 사용해 준다. queue는 먼저 들어간 값이 먼저 나오는 구조이다. 예를들어 어떤 서비스를 이용하기 위해 줄을 선다고 생각하면 먼저 줄 선 사람이 제일 빠르게 서비스를 이용할 수 있는 것과 똑같은 형식이다.

 

queue<pair<int,int> >로 queue안에 현재 위치, n초후 2가지 값을 넣을 수 있도록 자료형을 만들어주었다.

 

그리고 visit배열을 만들어서 한 번 방문한 위치는 다시 방문하지 않도록 하여 시간초과가 걸리지 않도록 설계하였다.

 

q에 n과 0을 넣고 q가 빌 때까지 반복한다. 반복문에서 visit[x] = 1;으로 중복으로 방문하지 않도록 체크해주었다.

 

현재 위치에서 x-1, x+1, x*2로 이동할 때 범위를 벗어나지 않고, 이미 방문하지 않았다면 q에 이동할 위치, num+1을 넣어주어서 탐색을 하였다.

 

처음 x==k 조건문이 실행이 되면 num이 가장 빠르게 k위치에 도착한 경우이므로 ans1에 num을 넣어주고 ans++을 해준다. 그리고 ans1<num이면 너비 우선 탐색 특징상 q에 남아있는 값들의 num값이 전부다 ans1<num이므로 break;로 반복문을 중지시켜준다.

 

ans1, ans2를 출력하면 정답이다.

---

#성능

---

#정리

너비 우선 탐색(bfs) 알고리즘을 사용한다는 것,

 

visit배열을 이용하여 중복탐색을 막아줘야 시간초과가 걸리지 않는다는 것,

 

탐색을 할 때, 적절한 조건문을 사용하면 풀 수 있는 문제였다.