https://www.acmicpc.net/problem/1697
시간 제한 | 메모리 제한 | solved.ac 티어 |
2초 | 128MB | 실버 1 |
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
이 문제는 푼지 꽤 됐는데, 어째서인지 글이 안써져 있었다. 그래서 간단하게 작성한다.
이 문제는 처음보면 그래프탐색인걸 몰랐다. 이 문제를 풀때는 최단거리라는 알고리즘 개념은 없었지만, 어째서인지 bfs를 돌리다가 맨 처음 K를 찾으면, 그게 답일 것 같았다. 머리속에서도 그래프를 그려보니 맞는 것 같아 bfs를 돌려봤다. 왜 bfs로 찾은 거리가 최단거리냐면, 간선의 가중치가 모두 같기 때문이다.(이건 이 문제를 풀고 한참 있다가 알게 되었다.)
#include <bits/stdc++.h>
#define MAX 100001
using namespace std;
void solution(int start, int target, int time) {
int ans;
bool visited[MAX] = {false, };
queue<pair<int, int>> q; // pair -> (location, time)
q.push(make_pair(start, 0));
visited[start] = true;
while(!q.empty()) {
int loc = q.front().first;
int t = q.front().second;
q.pop();
if (loc == target) {
ans = t;
break;
}
if (loc + 1 < MAX && !visited[loc + 1]) {
q.push(make_pair(loc + 1, t + 1));
visited[loc + 1] = true;
}
if (loc * 2 < MAX && !visited[loc * 2]) {
q.push(make_pair(loc * 2, t + 1));
visited[loc * 2] = true;
}
if (loc - 1 >= 0 && !visited[loc - 1]) {
q.push(make_pair(loc - 1, t + 1));
visited[loc - 1] = true;
}
}
cout << ans;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int start, target;
cin >> start >> target;
solution(start, target, 0);
}
문제풀면 바로바로 쓰자...
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 2075번 C++ 풀이 (0) | 2022.07.31 |
---|---|
백준 13549번 C++ 풀이 (0) | 2022.07.27 |
백준 1543번 C++ 풀이 (0) | 2022.07.12 |
백준 11659번 C++ 풀이 (0) | 2022.06.29 |
백준 2644번 C++ 풀이 (0) | 2022.06.29 |