#문제
12851번: 숨바꼭질 2
https://www.acmicpc.net/problem/12851
#접근방법
너비 우선 탐색(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배열을 이용하여 중복탐색을 막아줘야 시간초과가 걸리지 않는다는 것,
탐색을 할 때, 적절한 조건문을 사용하면 풀 수 있는 문제였다.
'하루 한 문제' 카테고리의 다른 글
[백준] 13172번 : Σ [C/C++] (0) | 2022.01.15 |
---|---|
[백준] 12865번 : 평범한 배낭 [C/C++] (0) | 2022.01.12 |
[백준] 9663번 : N-Queen [C/C++] (0) | 2021.12.26 |
[백준] 9251번 : LCS [C/C++] (0) | 2021.12.26 |
[백준] 1916번 : 최소비용 구하기 [C/C++] (0) | 2021.12.23 |