백준 13549번 숨바꼭질 3 - 자바(Java)

문제 링크

https://www.acmicpc.net/problem/13549

 

---

1. 문제

n과 k가 주어지고 n을 k값으로 만들려고 할때 +1, -1 , *2를 할 수 있을때

+1, -1은 cost가 1 들게 되지만

*2는 비용이 들지 않는다.

 

이때 최소 비용으로 k를 만드는 문제였다.

 N(0 ≤ N ≤ 100,000)

 K(0 ≤ K ≤ 100,000)

2. 문제 관찰 과정 및 풀이

 

2-1. 문제 관찰 과정

최단 거리를 구하는 문제 이기 때문에 bfs를 떠올리게 되었고

수만 주어지기 때문에 hashset으로 방문을 했었는지 확인하였다.

2-2. 문제 풀이

1. start와 end를 매개 변수로 받는 bfs메서드
2. count를 각 경로마다 카운트하기 위해 node클래스를 만들어서 관리
3. 시작하는 노드를 큐에 넣고 방문으로 표시
4. while문을 돌면서 큐에서 꺼내어 방문으로 표시 후 목적지인지 확인후 count값을 비교
   1. 현재 값에서 2배한 값의 +1 보다 작거나 같다면( +1 할것까지 고려)
      1. 큐에 *2한 값을 넣어준다.
   2. 현재 값에서 +1 한 값이 N의 범위 보다 작으면서 end값보다 작거나 같다면(넘어가면 또 -1 해주어야함 무한 반복)
      1. 큐에 +1 한 값 대입 count +1
   3. 현재 값에서 -1 한 값이 0 보다크다면
      1. 큐에 -1 한 값 대입 count + 1

3. 코드

import java.io.*;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static final int MAX =  100000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        //n에 +1 -1, *2를 해서 k가 되도록
        //*2는 무료 +1, -1 는 cost 1

        int result = bfs(n, k);

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int bfs(int start, int end){
        class Node{
            int count  = 0;
            int index;
            Node(int index, int count){
                this.index = index;
                this.count = count;
            }
        }
        Queue<Node> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        int min = Integer.MAX_VALUE;
        queue.add(new Node(start, 0));
        visited.add(start);
        while(!queue.isEmpty()){
            Node tmp = queue.poll();
            if(tmp.index == end){ //도달
                if(tmp.count < min){
                    min = tmp.count;
                }
            }

            if(tmp.index * 2 <= end + 1 && !visited.contains(tmp.index * 2) && tmp.index != 0){ //2배 +1 보다 작거나 같다면
                queue.add(new Node(tmp.index * 2, tmp.count));
                visited.add(tmp.index * 2);
            }
            if ( tmp.index -1 >= 0 && !visited.contains(tmp.index - 1)  ) {
                queue.add( new Node(tmp.index -1 , tmp.count +1 ));
                visited.add(tmp.index - 1);
            }
            if(tmp.index + 1 <= end && tmp.index +1 <= MAX  && !visited.contains(tmp.index + 1)){
                queue.add(new Node(tmp.index + 1, tmp.count + 1 ));
                visited.add(tmp.index + 1);
            }


        }
        return min;
    }
}

3-1. 실행 결과

4. 여담

여러가지 바꾸다 보니 좀더 if문을 좀더 깔끔하게 할 수 있지 않았을까 싶고

지금 보니 왜 *2 +1 해야했는지 정확히 기억나지 않는다...