[백준](Java) 1697 - 숨바꼭질

문제 링크

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

문제 풀이

맨처음 문제를 보고 수학문제로 공식을 이용해서 접근할수 있지 않을까 했는데 문제 분류가 bfs였기에 그렇게 접근해 보았다.

만약에 시작우치ㅣ가 도착 위치보다 큰경우에는 뒤로 가는경우밖에 없으므로
n-k를 출력하고
나머지 경우에 bfs를 돌기 시작하게 한다.

        if(n>k){
            System.out.println(n-k);
        }else{
            bfs(n,0);
            System.out.println(answer);
        }

현재 위치와 시간을 나타내는 class Node를 만든다.

    static class Node{
        int pos;
        int time;
        public Node(int pos, int time){
            this.pos=pos;
            this.time=time;
        }
    }

이동하는 위치에 대한 정보를 queue에다가 담기위해 Node를 자료형으로 가지는 Queue 선언 최초의 값을 넣어준다.
map은 한번 방문한 칸인지 체크하기 위해서 선언했다. map의 key는 위치값, value는 그때의 시간을 저장한다. 그래서 이동하고 난 위치가 map의 key에 있는지 체크하고 key에 없을경우에는 그대로 map.put 해주지만 이미 방문한적이 있는경우 서로의 시간값을 비교하여
map에 저장된 시간보다 현재 시간값이 큰경우 더이상 방문할 필요가 없으므로 저장하지 않는다.

            if(!map.containsKey(now.pos+1)){
                queue.add(new Node(now.pos+1,now.time+1));
                map.put(now.pos+1,now.time+1);
            }else{
                if(map.get(now.pos+1)>now.time+1){
                    queue.add(new Node(now.pos+1,now.time+1));
                    map.put(now.pos+1,now.time+1);
                }
            }
            if(!map.containsKey(now.pos-1)){
                queue.add(new Node(now.pos-1,now.time+1));
                map.put(now.pos-1,now.time+1);
            }else{
                if(map.get(now.pos-1)>now.time+1){
                    queue.add(new Node(now.pos-1,now.time+1));
                    map.put(now.pos-1,now.time+1);
                }
            }
            if(!map.containsKey(now.pos*2)){
                queue.add(new Node(now.pos*2,now.time+1));
                map.put(now.pos*2,now.time+1);
            }else{
                if(map.get(now.pos*2)>now.time+1){
                    queue.add(new Node(now.pos*2,now.time+1));
                    map.put(now.pos*2,now.time+1);
                }
            }

현재위가 0보다 작아지게 되면 바로 종료, k와 같아지게 되거나, k보다 커지게 되면 각각의 조건에 맞게 answer 값을 구한다.

            if(now.pos>k){
                answer = Math.min(answer, now.time + now.pos-k);
                continue;
            }
            if(now.pos<0){
                continue;
            }
            if(now.pos==k){
                answer = Math.min(answer,now.time);
                continue;
            }

코드

import java.util.*;

public class Main {

    static int n;
    static int k;
    static int answer = Integer.MAX_VALUE;
    static Map<Integer,Integer> map = new HashMap();
    static class Node{
        int pos;
        int time;
        public Node(int pos, int time){
            this.pos=pos;
            this.time=time;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        if(n>k){
            System.out.println(n-k);
        }else{
            bfs(n,0);
            System.out.println(answer);
        }
        
    }

    public static void bfs(int idx, int time){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(idx,time));
        map.put(idx,0);
        while(!queue.isEmpty()){
            Node now = queue.poll();
            //System.out.println(now.pos+" "+now.time);
            if(now.pos>k){
                answer = Math.min(answer, now.time + now.pos-k);
                continue;
            }

            if(now.pos<0){
                continue;
            }

            if(now.pos==k){
                answer = Math.min(answer,now.time);
                continue;
            }

            if(!map.containsKey(now.pos+1)){
                queue.add(new Node(now.pos+1,now.time+1));
                map.put(now.pos+1,now.time+1);
            }else{
                if(map.get(now.pos+1)>now.time+1){
                    queue.add(new Node(now.pos+1,now.time+1));
                    map.put(now.pos+1,now.time+1);
                }
            }

            if(!map.containsKey(now.pos-1)){
                queue.add(new Node(now.pos-1,now.time+1));
                map.put(now.pos-1,now.time+1);
            }else{
                if(map.get(now.pos-1)>now.time+1){
                    queue.add(new Node(now.pos-1,now.time+1));
                    map.put(now.pos-1,now.time+1);
                }
            }

            if(!map.containsKey(now.pos*2)){
                queue.add(new Node(now.pos*2,now.time+1));
                map.put(now.pos*2,now.time+1);
            }else{
                if(map.get(now.pos*2)>now.time+1){
                    queue.add(new Node(now.pos*2,now.time+1));
                    map.put(now.pos*2,now.time+1);
                }
            }

        }

    }
}