728x90
📌 문제
문제) 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다.
수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력)
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.
N과 K는 정수이다.
출력)
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
시간 제한 : 2초
메모리 제한 : 512 MB
📌 문제 분석❗️
첫째 줄에 수빈이의 위치 N, 동생의 위치 K가 주어진다.
곰곰히 생각해보자.
어떤 지점에서 수빈이가 이동할 수 있는 경우는
1. 순간이동(2 * N, 0초)
2. 한칸 이동(N + 1, 1초)
3. 한칸 이동(N - 1, 1초)
세가지가 있다.
동생의 위치에 도달하는 경우는 위의 세가지 경우를 어떻게 조합해서 도착하면 된다.
가장 간단한 방법은 경우의 수를 모두 탐색해보는 것이다. 해당 방법은 bfs 방법과 같다.
if (curNode.idx == K) {
result = curNode.time;
}
if (curNode.idx * 2 <= 100_000) {
que.offer(new Node(curNode.idx * 2, curNode.time));
}
if (curNode.idx + 1 <= 100_000) {
que.offer(new Node(curNode.idx + 1, curNode.time + 1));
}
if (curNode.idx - 1 >= 0) {
que.offer(new Node(curNode.idx - 1, curNode.time + 1));
}위 코드와 같이 queue에 계속 offer하여 가능한 모든 범위를 따져보는 것이다. 근데 이러면 동생을 찾긴 하겠는데, 결과 값(result)가 최소 비용이 아닌 동생을 찾을 때마다 값이 덮여진다.
그래서,
해당 위치를 방문했는지와 여부와 특별히, 이전에 최적 경로를 탐색했던 방법에서 PriorityQueue를 사용했던 것을 활용해서 결과 값에는 최소의 비용이, 그리고 방문한 위치는 다시 방문하지 않는다는 조건을 걸어줘야 한다.
시간을 기준으로 오름차순 정렬, PriorityQueue를 사용하면 큐에서 poll 하는 순간 최소 비용의 노드를 먼저 뽑게 되므로 동생을 찾게될 경우 제일 적게 걸린 시간이 결과 값에 담기게 될 것이다. 해당 부분에 방문 여부만 체크해주면 다시는 방문하지 않으므로 값이 덮어씌어질 우려가 없다.
해당 내용을 통해 코드를 구현해보자.
📌 진행
노드의 구현, PriorityQueue에 사용할 정렬을 구현해준다.
static class Node implements Comparable<Node> {
int idx;
int time;
public Node(int idx, int time) {
this.idx = idx;
this.time = time;
}
@Override
public int compareTo(Node o) {
return this.time - o.time;
}
}노드에는 해당 위치(idx)와 해당 위치에 도착할 때까지 누적된 경과 시간(time)의 정보가 담겨있다.
전역변수 선언
private static int result = 0; // 결과 값
private static boolean[] isVisited = new boolean[100_001]; // 방문 여부결과 값을 담아줄 result 변수와, 방문 여부(isVisited)를 체크할 배열을 전역으로 선언해준다.
BFS 구현
private static void bfs(int N, int K) {
PriorityQueue<Node> que = new PriorityQueue<>();
que.offer(new Node(N, 0)); // 수빈이 출발
while (!que.isEmpty()) {
Node curNode = que.poll();
// 방문 여부 체크
isVisited[curNode.idx] = true;
// 동생을 찾았다면 결과 값에 해당 경과 시간을 담아준 뒤 메서드를 종료한다.
if (curNode.idx == K) {
result = curNode.time;
return;
}
// 경계조건 1 : N * 2 <= 100000, 그리고 방문여부 체크
if (curNode.idx * 2 <= 100_000 && !isVisited[curNode.idx * 2]) {
que.offer(new Node(curNode.idx * 2, curNode.time));
}
// 경계조건 2 : N + 1 <= 100000, 그리고 방문여부 체크
if (curNode.idx + 1 <= 100_000 && !isVisited[curNode.idx + 1]) {
que.offer(new Node(curNode.idx + 1, curNode.time + 1));
}
// 경계조건 3 : N - 1 >= 0, 그리고 방문여부 체크
if (curNode.idx - 1 >= 0 && !isVisited[curNode.idx - 1]) {
que.offer(new Node(curNode.idx - 1, curNode.time + 1));
}
}
}
출력
public static void main(String[] args) throws IOException {
int N = readInt(); // 수빈이 위치
int K = readInt(); // 동생 위치
bfs(N, K);
System.out.println(result);
}
📌 전체 코드
package level27_최단_경로_.Q3_13549;
import java.io.IOException;
import java.util.PriorityQueue;
public class Main {
/*
힌트)
5 17
10 17 -> 순간이동
9 17 -> 한칸이동(1초)
18 17 -> 순간이동
17 17 -> 한칸이동
*/
static class Node implements Comparable<Node> {
int idx;
int time;
public Node(int idx, int time) {
this.idx = idx;
this.time = time;
}
@Override
public int compareTo(Node o) {
return this.time - o.time;
}
}
private static int result = 0; // 결과 값
private static boolean[] isVisited = new boolean[100_001]; // 방문 여부
public static void main(String[] args) throws IOException {
int N = readInt(); // 수빈이 위치
int K = readInt(); // 동생 위치
bfs(N, K);
System.out.println(result);
}
private static void bfs(int N, int K) {
PriorityQueue<Node> que = new PriorityQueue<>();
que.offer(new Node(N, 0)); // 수빈이 출발
while (!que.isEmpty()) {
Node curNode = que.poll();
// 방문 여부 체크
isVisited[curNode.idx] = true;
// 동생을 찾았다면 결과 값에 해당 경과 시간을 담아준 뒤 메서드를 종료한다.
if (curNode.idx == K) {
result = curNode.time;
return;
}
// 경계조건 1 : N * 2 <= 100000, 그리고 방문여부 체크
if (curNode.idx * 2 <= 100_000 && !isVisited[curNode.idx * 2]) {
que.offer(new Node(curNode.idx * 2, curNode.time));
}
// 경계조건 2 : N + 1 <= 100000, 그리고 방문여부 체크
if (curNode.idx + 1 <= 100_000 && !isVisited[curNode.idx + 1]) {
que.offer(new Node(curNode.idx + 1, curNode.time + 1));
}
// 경계조건 3 : N - 1 >= 0, 그리고 방문여부 체크
if (curNode.idx - 1 >= 0 && !isVisited[curNode.idx - 1]) {
que.offer(new Node(curNode.idx - 1, curNode.time + 1));
}
}
}
private static int readInt() throws IOException {
boolean isNegative = false;
int value = 0;
while (true) {
int input = System.in.read();
if (input == '\n' || input == ' ') {
return (isNegative) ? -1 * value : value;
} else if (input == '-') {
isNegative = true;
} else value = value * 10 + (input - 48);
}
}
}
댓글