728x90
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int N, K;
bool discovered[100001];
void bfs(int start){
queue<pair<int,int>> q;
discovered[start] = true;
q.push({start, 0});
while(!q.empty()){
pair<int, int> here = q.front();
q.pop();
if(here.first == K){
cout << here.second;
return;
}
int there;
there = here.first + 1;
if(0<=there && there<=100000){
if(!discovered[there]){
q.push({there, here.second+1});
discovered[there] = true;
}
}
there = here.first*2;
if(0<=there && there<=100000){
if(!discovered[there]){
q.push({there, here.second+1});
discovered[there] = true;
}
}
there = here.first - 1;
if(0<=there && there<=100000){
if(!discovered[there]){
q.push({there, here.second+1});
discovered[there] = true;
}
}
}
}
int main(void){
cin >> N >> K;
memset(discovered, false, sizeof(discovered));
bfs(N);
return 0;
}
문제 유형을 찾기 위해 몇가지 접근을 해보았다.
1. 완전탐색 => 시간초과
2. 동적 계획법 => 막상 dp를 적용하려 했으나 딱히 겹치는 부분도 없고 메모이제이션을 쓰기에도 애매해서 다른 방법 모색
3. dfs / bfs => 최소값을 구하는 문제이니 dfs보단 bfs가 낫다고 판단
결론, bfs를 사용하여 문제 풀이
아무래도 문제에 맞는 문법을 찾는게 가장 중요한것 같다. 나머지는 문법에 맞는 풀이를 끼워맞추면 되니 말이다...
*참고*
꿀팁 단축키를 몇가지 발견해서 써놓을려한다!
1. Ctrl + D : 똑같은 단어를 내려가면서 하나씩 선택할 수 있다.
2. Shift + Tap : Tap만큼 뒤로간다.
728x90
반응형
'PS > DFS, BFS' 카테고리의 다른 글
[7569] 토마토 (0) | 2023.06.03 |
---|---|
[7576] 토마토 (0) | 2023.06.03 |
[2178] 미로 탐색 (0) | 2023.05.25 |
[2667] 단지번호붙이기 (0) | 2023.05.23 |
[24444] 알고리즘 수업 - 너비 우선 탐색 1 (1) | 2023.05.23 |