성능 요약
Java - 메모리: 21880 KB, 시간: 192 ms
C++ - 메모리: 3000 KB, 시간: 4 ms
분류
0-1 너비 우선 탐색, 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로
제출 일자
2024년 12월 20일 22:55:45
문제 설명
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
풀이
느낀점
- BFS+DP 라고 생각했는데 그게 다익스트라였다.
- 숨바꼭질 어렵다고 생각했던 문제라서 쫄았는데 스스로 풀어서 뿌듯하다.
설계 : 15분
- 연산 순서와 횟수에 따라 경우의 수가 너무 많아서 다 확인해야 하지만 효과적인 방법 필요
- BFS로 차례차례 다음 연산을 시도하면 가장 적은 횟수의 결과부터 방문하게 될것이다.
- 하지만 연산 종류에 따라 횟수 추가 여부가 일정하지 않기 때문에 방문하기 전 연산 횟수에 따른 정렬이 필요하다.
- 우선순위큐를 통해 연산횟수가 적은 결과부터 방문한다.
- dp테이블을 이용해 각 위치에 도달할 수 있는 최소 연산 횟수를 갱신하며, 더 많은 연산횟수로 도달하려고 시도하면 건너뛴다.
- 하지만 단순히 최단 경로라고 생각하면 바로 다익스트라를 떠올릴 수 있긴 하다.
코드(Java)
- 구현 시간: 20분
/**
* Author: yngbao97, Yuk Yejin
* Problem: 숨바꼭질 3_13549
* Date: 2024.12.20
*/
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
int[] dp = new int[150_001];
Arrays.fill(dp, Integer.MAX_VALUE);
String[] input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.offer(new Node(start, 0));
dp[start] = 0;
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (curr.num == end) break;
if (curr.num > 0 && dp[curr.num - 1] > curr.count + 1) {
dp[curr.num - 1] = curr.count + 1;
queue.add(new Node(curr.num - 1, dp[curr.num - 1]));
}
if (curr.num < 150_000 && dp[curr.num + 1] > curr.count + 1) {
dp[curr.num + 1] = curr.count + 1;
queue.add(new Node(curr.num + 1, dp[curr.num + 1]));
}
if (curr.num < 75_000 && dp[curr.num * 2] > curr.count) {
dp[curr.num * 2] = curr.count;
queue.add(new Node(curr.num * 2, dp[curr.num * 2]));
}
}
bw.write(String.valueOf(dp[end]));
bw.flush();
bw.close();
br.close();
}
}
class Node implements Comparable<Node> {
int num;
int count;
Node(int num, int count) {
this.num = num;
this.count = count;
}
@Override
public int compareTo (Node o) {
return Integer.compare(this.count, o.count);
}
}코드(C++)
- 구현 시간: 20분
/**
* Author: yngbao97, Yuk Yejin
* Problem: 숨바꼭질 3_13549
* Date: 2024.12.20
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
#include <queue>
using namespace std;
struct compareCount {
bool operator() (const pair<int, int>& p1, const pair<int, int>& p2) {
return p1.second > p2.second;
}
};
int main() {
int start, end;
cin >> start >> end;
vector<int> dp(150001);
fill(dp.begin(), dp.end(), INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int> >, compareCount> pq;
pq.push(make_pair(start, 0));
dp[start] = 0;
while (!pq.empty()) {
pair<int, int> curr = pq.top();
pq.pop();
if (curr.first == end) break;
if (curr.first > 0 && dp[curr.first - 1] > curr.second + 1) {
dp[curr.first - 1] = curr.second + 1;
pq.push(make_pair(curr.first - 1, dp[curr.first - 1]));
}
if (curr.first < 150000 && dp[curr.first + 1] > curr.second + 1) {
dp[curr.first + 1] = curr.second + 1;
pq.push(make_pair(curr.first + 1, dp[curr.first + 1]));
}
if (curr.first < 75000 && dp[curr.first * 2] > curr.second) {
dp[curr.first * 2] = curr.second;
pq.push(make_pair(curr.first * 2, dp[curr.first * 2]));
}
}
cout << dp[end];
return 0;
}- 알게된 점
- pair의 선언은
pair<자료형, 자료형> 변수명이고, 초기화는make_pair(first, second)로 한다. - pair는 헤더를 include 해야한다.
- pair의 선언은
