📕문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.
📗입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
📗출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
🔎문제 해석
문제를 읽어보면 동생을 찾을 수 있는 가장 빠른 방법을 요구한다.
--> BFS 알고리즘을 사용해야 한다는 것을 여기서 유추해야 합니다.
3가지의 방법(+1,-1,*2)으로 계속 탐색해서 도착지에 도착하는지 검사하면 되는 문제입니다.
💡문제 풀이
- 이동 방법은 3가지입니다.
- {좌표+1, 좌표 -1, 좌표 *2}이고 모두 소요시간은 1초로 동일합니다.
- 우리는 현재 지역에서 갈 수 있는 3가지의 방법으로 탐색을 시작합니다.
- 방문 체크
- 중복되는 작업을 피하기 위해서 방문처리를 해줘야 합니다.
- 저는 그 지역을 방문했다면 그때의 시간을 기록해서, 큐에 넣기 전에 시간대를 계속 비교해서
시간이 더 짧은 시간에 방문했다면 큐에 넣고, 방문시간을 업데이트해줬습니다. - 만약 방문했는데, 기록된 시간보다 더 크다면, 굳이 큐에 넣어줄 필요가 없습니다.
- 저는 그 지역을 방문했다면 그때의 시간을 기록해서, 큐에 넣기 전에 시간대를 계속 비교해서
- 중복되는 작업을 피하기 위해서 방문처리를 해줘야 합니다.
- 도착 지점
- 만약 도착지점에 도착했다면, 그때의 시간을 기록해줘야 합니다.
- 문제에서 도착지점에 도착한 가장 빠른 시간대의 시간을 원하기 때문에, 계속 도착했다면 기록된 시간과
비교해 주는 작업을 해야 합니다.
- 문제에서 도착지점에 도착한 가장 빠른 시간대의 시간을 원하기 때문에, 계속 도착했다면 기록된 시간과
- 만약 탐색하려는 지역의 시간대가 , 기록된(도착지점) 시간대보다 크다면 검사할 필요가 없기 때문에 검사를 생략합니다.
- 만약 도착지점에 도착했다면, 그때의 시간을 기록해줘야 합니다.
❌주의할 점
해당 문제는 쉽지만, 좌표에 바운더리가 크기 때문에 최적화를 잘해줘야 합니다.
(저도 최적화 때문에 한번 틀린 경험이...)
최대한 탐색의 경우의 수를 줄여야 하기에, 방문체크, 도착 지점에 대한 시간대 기록을 해줬습니다.
💻코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
int x, y;
queue<pair<int, int>> q;
void funct();
int ans = 0;
int mintime = INT_MAX;
int main()
{
cin >> x >> y;
q.push(make_pair(0, x)); // {시간, 좌표} -> 를 q에 넣음.
funct();
cout << mintime << "\n" << ans << endl;
}
void funct()
{
vector<int> visit(1000001, INT_MAX); //시간대를 계속 최소값으로 업데이트 해주기 위한 초기값 설정
visit[x] = 0;
while (!q.empty())
{
int time = q.front().first;
int location = q.front().second;
q.pop();
if (time > mintime){ //도착했을때의 시간대보다 길다면 검사를 생략
break;
}
if (visit[location] < time){ //방문한 지역이 이미 방문했다면 == 시간대가 더 크다면 생략.
continue;
}
visit[location] = time; //방문 처리. 시간대를 기록.
if (location == y && time <= mintime){ // 처음으로 도착햇다면, 그때의 시간을 기록해두자.
ans++;
mintime = time;
continue;
}
//아래 코드는 모두 이동하는 위치가 범위를 벗어나지 않고, 시간을 업데이트 해줄 필요성이 있을 때의 작업.
if (location * 2 <= 100000 && visit[location * 2] >= time + 1){
q.push(make_pair(time + 1, location * 2));
visit[location * 2] = time + 1;
}
if (location - 1 >= 0 && visit[location - 1] >= time + 1){
q.push(make_pair(time + 1, location - 1));
visit[location - 1] = time + 1;
}
if (location + 1 <= 100000 && visit[location + 1] >= time + 1){
q.push(make_pair(time + 1, location + 1));
visit[location + 1] = time + 1;
}
}
}
😀느낀 점
- 처음에는 시간대를 하나하나 업데이트해주는 작업을 생략하기 위해서 우선순위 큐를 사용해서, 시간을 기준으로 정렬하는 작업을 했습니다.
- 이렇게 되면 하나하나 시간대를 비교해 주는 작업을 안 해줘도 된다고 생각했는데, 시간초과라는...
- 아마 그때 최적화를 덜 한 상태여서,, 그런 거 같기도 합니다. 우선순위큐를 사용해도 될 거 같습니다.
- 최적화 때문에 애를 좀 먹었습니다... 저는 4ms인데,, 생각보다 0ms인 분들도 많더라고요,, 자괴감이 드네
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준 14719] - 빗물(C++)[골드5] (0) | 2023.03.07 |
---|---|
[백준 21758] - 꿀 따기(C++)[골드5] (0) | 2023.03.06 |
[백준 1976] - 여행가자(C++)[골드4] (0) | 2023.03.04 |
[백준 5427] - 불(C++)[골드4] (0) | 2023.03.02 |
[백준 1513] - 경로찾기(C++)[골드2] (0) | 2023.02.28 |