문제 이해 단계
문제 자체는 짧고 이해도 간단한 문제.
X축 하나만 존재하고 점 N에서 점 K까지 가는데 총 3가지 방법이 존재한다.
1. 2 * N칸 이동 -> 시간소모 = 0초
2. +1칸 이동 -> 시간소모 = 1초
3. -1칸 이동 -> 시간 소모 = 1초
이 세 가지 방법을 이용하여, 점 N에서 점 K까지 가는 최소 시간을 찾는 문제이다.
문제 접근 단계
처음에는 최소시간을 찾는 것이기 때문에 그리디 문제인 줄 알았다.
하지만 그리디 문제의 조건은 매 순간마다의 최적의 답이 문제의 답이 되어야 한다.
이 문제에서는 나중에 분석한 답이 더 최소 시간 일수도 있기 때문에
그리디로 풀기엔 적합하지 않다.
그래서 x축에서 한 점을 기준으로 양쪽을 탐색하여 K를 찾는 BFS 방식을 사용하기로 했다.
다른 BFS 문제와 다르게 이동하는 데에 가중치가 존재한다.
2x로 이동하는 데는 0의 비용이 존재하고,
(x+1)과 (x-1)에는 1의 비용이 존재한다.
즉, 2x가 (x+1)과 (x-1)보다 우선순위가 높다.
이게 뜻하는 말은 한 칸씩 이동하는 탐색보다
두 배씩 이동하는 탐색이 먼저 수행되어야 한다는 뜻이다.
이를 구현하기 위해서 덱 또는 우선순위 큐를 사용해야 하는데, 이번에는 덱을 사용하였다.
2x 작업을 할 때는 덱 앞에서 넣어주고, x+1이나 x-1을 넣어줄 때는 덱 뒤에서 넣어준다.
덱에서 뽑는 작업을 할 때는 덱 앞에서부터 뽑아, 무조건 2x작업이 먼저 수행되도록 해준다.
문제 구현 단계
int N, K;
int dx[] = { -1,1 };
int visit[100001];
int answer = 0;
cin >> N >> K;
deque<int> dq;
dq.push_back(N);
visit[N] = 1;+- 작업을 해줄 배열 dx []와 방문 처리를 담당할 visit,
그리고 덱을 선언한 뒤, 입력 N을 큐에 넣고 visit을 1로 초기화해 준다.
여기서 visit은 방문처리를 뜻하기도 하지만, 방문 최소 시간을 담는 배열이기도 하다.
while (!dq.empty()) {
int x = dq.front();
if (x == K) {
answer = visit[x] - 1;
break;
}
dq.pop_front();
if (2 * x < 100001 && !visit[2 * x]) {
visit[2 * x] = visit[x];
dq.push_front(2 * x);
}
for (int i = 0; i < 2; i++) {
int nx = x + dx[i];
if (nx > 100000 || nx < 0 || visit[nx]) continue;
dq.push_back(nx);
visit[nx] = visit[x] + 1;
}
}
cout << answer;BFS를 하는 부분이다.
기본적인 BFS방식과 동일하나, 덱에서 빼낸 값이 K와 동일하면 그 값에서 -1을 해준다.
왜냐하면 시간은 0초부터 시작해야 하는데 방문처리 때문에 1로 초기화했기 때문이다.
이후에는 2x가 최대범위 안에 있고 방문하지 않았으면, x에 있던 시간 정보 그대로를 2x에 전달하고 덱 앞에 넣는다.
x+1, x-1인 경우에는 2x와 똑같은 작업을 하는데 시간정보 + 1을 전달하고 덱 뒤에 넣는다.
이 작업을 덱이 빌 때까지 혹은, x가 K값과 같아질 때까지 반복한다.
밑에는 전체코드를 올려두고 끝내겠다.
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int main() {
int N, K;
int dx[] = { -1,1 };
int visit[100001];
int answer = 0;
cin >> N >> K;
deque<int> dq;
dq.push_back(N);
visit[N] = 1;
while (!dq.empty()) {
int x = dq.front();
if (x == K) {
answer = visit[x] - 1;
break;
}
dq.pop_front();
if (2 * x < 100001 && !visit[2 * x]) {
visit[2 * x] = visit[x];
dq.push_front(2 * x);
}
for (int i = 0; i < 2; i++) {
int nx = x + dx[i];
if (nx > 100000 || nx < 0 || visit[nx]) continue;
dq.push_back(nx);
visit[nx] = visit[x] + 1;
}
}
cout << answer;
}
시행착오
그래프 탐색 문제 중에서 우선순위가 존재하는, 가중치가 존재하는 문제는 처음이었다.
엄청 시간이 오래 걸려서 풀었으나 메모리초과, 틀렸습니다 등,
내 선에서는 도저히 풀 수가 없었다.
결국에는 인터넷을 참고할 수밖에 없었다.
신선한 문제였기도 하고 이제 이런 문제도 풀어봤으니 앞으로는 좀 더 쉽게 풀 수 있을 것 같다.