[백준]13549: 숨바꼭질 3 - JAVA

[백준]13549: 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

풀이

탐색 문제로 문제 조건에 따라 탐색 조건을 적절하게 작성해서 탐색한다. 최소비용을 찾는 문제이므로 BFS를 사용하였다.

진행되는 연산은 3종류로 +1, -1, *2이다. 이때 연산 순서도 중요하다. 

예를들어 현재 노드의 값이 1이고 목적 노드의 값이 2일 경우에 +1보다 *2가 수행되는 경우가 최소비용이기 때문이다.

 

이 점만 유의하면 된다. 나머지는 일반적인 BFS탐색 문제와 동일하다.

 

코드

import java.util.*;
 
public class Main {    
 
    static int min = Integer.MAX_VALUE;
    static int n, k;
    static boolean[] visited;
    static int max = 100000;
    
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        k = scan.nextInt();
        
        visited = new boolean[max + 1];
        bfs();
        System.out.println(min);
    }
    
    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(n, 0));
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            visited[node.x] = true;
            if(node.x == k) min = Math.min(min, node.time);
            
            if(node.x * 2 <= max && visited[node.x * 2] == false) q.offer(new Node(node.x * 2, node.time));
            if(node.x + 1 <= max && visited[node.x + 1] == false) q.offer(new Node(node.x + 1, node.time + 1));
            if(node.x - 1 >= 0 && visited[node.x - 1] == false) q.offer(new Node(node.x - 1, node.time + 1));
        }
    }
    
    public static class Node {
        int x;
        int time;
        
        public Node(int x, int time) {
            this.x = x;
            this.time = time;
        }
    }
}