백준 문제풀이

[Baekjoon 13549] 숨박꼭질 3 - JAVA

planting grass 2023. 6. 2. 12:44
728x90

[Gold V] 숨바꼭질 3 - 13549

문제 링크

성능 요약

메모리: 87016 KB, 시간: 272 ms

분류

0-1 너비 우선 탐색, 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

문제 풀이

BFS 탐색 중에 순간이동을 할 수 있는 경우를 가장 먼저 계산하여 처리해야 한다. 순간이동은 시간이 소요되지 않기 때문에, 다른 방향으로 이동하는 경우보다 먼저 처리돼야 하기 때문이다. 그렇지 않으면 방문 처리가 되어있는 상태에서 순간이동이 가능한 위치에 대해 큐에 추가되지 않게 되어, 실제로 방문할 수 있는 시간보다 높은 값을 저장하게 된다.

따라서, 순간이동을 처리하는 로직이 다른 이동 방향보다 먼저 실행되도록 코드를 작성해야 한다. 이를 위해 코드에서 순간이동을 처리하는 부분을 다른 이동 방향보다 앞에 위치시켜야 한다.

코드에 아래 내용이 그 역할을 수행한다.

        if (N * 2 <= max && !visited[N * 2]) {
            queue.offer(new Node(N * 2, 0));
            visited[N * 2] = true;
        }

위의 코드에서는 순간이동을 먼저 처리하고, 그 다음에 다른 이동 방향을 처리하도록 구성되어 있습니다. 이렇게 하면 순간이동이 가능한 위치에 대해 먼저 방문 처리되고 큐에 추가되므로, 올바른 결과를 얻을 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q13549 {
    static int min = Integer.MAX_VALUE;
    static int N, K;
    static boolean[] visited;
    static int max = 100000;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        visited = new boolean[max + 1];
        bfs();
        System.out.println(min);
    }

    public static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(N, 0));

        if (N * 2 <= max && !visited[N * 2]) {
            queue.offer(new Node(N * 2, 0));
            visited[N * 2] = true;
        }

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            visited[node.position] = true;
            if (node.position == K)
                min = Math.min(min, node.time);

            if (node.position * 2 <= max && !visited[node.position * 2])
                queue.offer(new Node(node.position * 2, node.time));
            if (node.position + 1 <= max && !visited[node.position + 1])
                queue.offer(new Node(node.position + 1, node.time + 1));
            if (node.position - 1 >= 0 && !visited[node.position - 1])
                queue.offer(new Node(node.position - 1, node.time + 1));
        }
    }

    public static class Node {
        int position;
        int time;

        public Node(int position, int time) {
            this.position = position;
            this.time = time;
        }
    }
}

코드 풀이

static int min = Integer.MAX_VALUE;
static int N, K;
static boolean[] visited;
static int max = 100000;
  • 최소시간을 나타낼 변수 min을 선언
  • 출발 위치와 도착 위치를 나타낼 변수 N과 K를 선언
  • 방문한 위치를 기록한 배열 visited를 선언
  • 위치할 최댓값 max를 선언
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

    visited = new boolean[max + 1];
    bfs();
    System.out.println(min);
}
  • N과 K에 값을 입력받는다.
  • visited 배열을 max + 1 크기로 초기화힌다.
  • bfs() 메서드를 호출한다.
  • 최소시간인 min 값을 출력한다.
public static void bfs() {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node(N, 0));

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        visited[node.position] = true;
        if (node.position == K)
            min = Math.min(min, node.time);

        if (node.position * 2 <= max && !visited[node.position * 2])
            queue.offer(new Node(node.position * 2, node.time));
        if (node.position + 1 <= max && !visited[node.position + 1])
            queue.offer(new Node(node.position + 1, node.time + 1));
        if (node.position - 1 >= 0 && !visited[node.position - 1])
            queue.offer(new Node(node.position - 1, node.time + 1));
    }
}
  • Queue 인터페이스를 구현한 LinkedList 객체 queue를 생성한다.
  • offer()를 사용하여 초기 노드를 큐에 추가한다.
  • 출발 위치의 2배인 위치로 순간이동하는 경우를 가장 먼저 계산하기 위해 큐에 추가한다. 이때, 해당 위치가 최댓값(max)보다 작거나 같고 방문되지 않았을 때만 추가한다.
  • 큐가 비어있지 않은 동안 반복한다.
  • poll()을 사용하여 큐에서 노드를 꺼내온다.
  • visited를 true로 바꿔 현재 노드의 위치를 방문한 것으로 표시한다.
  • 만약 현재 노드의 위치가 목표 위치 K와 같다면, min과 node.time 중 작은 값을 선택해 min을 바꿔준다.
  • 현재 노드의 위치에서 2배를 한 값이 최대값 max보다 작거나 같고, 해당 위치를 방문하지 않았다면, 큐에 새로운 노드를 추가한다.
  • 현재 노드의 위치에 1을 더한 값이 최대값 max보다 작거나 같고, 해당 위치를 방문하지 않았으면, 큐에 새로운 노드를 추가한다.
  • 현재 노드의 위치에서 1을 뺀 값이 0보다 크거나 같고, 해당 위치를 방문하지 않았다면, 큐에 새로운 노드를 추가한다.
public static class Node {
    int position;
    int time;

    public Node(int position, int time) {
        this.position = position;
        this.time = time;
    }
}
  • Node 클래스다. 이 클래스는 노드의 위치(position)와 시간(time) 정보를 가지고 있다.
  • Node 클래스의 생성자를 정의해서 position과 time 값을 초기화한다.
728x90
저작자표시