숨바꼭질 3 -13529번

---

풀이 방법

2배로 갈때와 1칸 이동할때 가중치가 다르다고 생각해서 다익스트라 알고리즘을 사용해서 풀어야 겠다고 생각했다. 

Node에 위치와 그 위치에 도달할 때 1초가 걸리는 지 0초가 걸리는지 넣어주었다. 위치에 도달하기 위해 걸리는 총 시간은 sec배열에 넣어서 구현했다.

풀다보니 BFS로도 가능할거 같다는 생각이 들어서 BFS로도 풀어보았다. 

BFS에선 Node에 sec를 그 위치에 걸리는 총 시간을 넣어서 sec 배열을 사용하지 않았다. 

가중치가 다르긴 하지만 규칙이 있는 가중치라서 BFS로도 가능하게 풀이된 것으로 보인다.

 

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

class Node {
    private int N;
    private int sec;

    public Node(int n, int sec) {
        N = n;
        this.sec = sec;
    }

    public int getSec() {
        return sec;
    }

    public int getN() {
        return N;
    }
}

public class Main {

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

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

        int sec = 0;

        Boolean[] visited = new Boolean[100001];
        Arrays.fill(visited, false);

        Queue<Node> q = new LinkedList<>();
        Node node = new Node(N, 0);

        q.offer(node);
        visited[N] = true;

        while (!q.isEmpty()) {
            node = q.poll();
            N = node.getN();
            sec = node.getSec();

            if (N == K) {
                System.out.println(sec);
                return;
            }

            if (N * 2 <= 100000 && !visited[N * 2]) {
                q.offer(new Node(N * 2, sec));
                visited[N * 2] = true;
            }
            if (N - 1 >= 0 && !visited[N - 1]) {
                q.offer(new Node(N - 1, sec + 1));
                visited[N - 1] = true;
            }
            if (N + 1 <= 100000 && !visited[N + 1]) {
                q.offer(new Node(N + 1, sec + 1));
                visited[N + 1] = true;
            }
        }
    }
}

import java.io.*;
import java.sql.Array;
import java.util.*;

class Node implements Comparable<Node> {
    private int N;
    private int sec;

    public Node(int n, int sec) {
        N = n;
        this.sec = sec;
    }

    public int getSec() {
        return sec;
    }

    public int getN() {
        return N;
    }

    @Override
    public int compareTo(Node other) {
        if (this.sec < other.sec)
            return -1;
        return 1;
    }
}

public class Main {

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static Boolean[] visited = new Boolean[100001];
    static int[] sec = new int[100001];
    static int K, N;

    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());

        Arrays.fill(visited, false);
        Arrays.fill(sec, (int) 1e9);

        for (int i = 0; i <= 100000; i++) {
            graph.add(new ArrayList<Node>());
        }

        for (int i = 0; i <= 100000; i++) {
            if (i != 0 && i * 2 <= 100000)
                graph.get(i).add(new Node(i * 2, 0));
            if (i + 1 <= 100000)
                graph.get(i).add(new Node(i + 1, 1));
            if (i - 1 >= 0)
                graph.get(i).add(new Node(i - 1, 1));
        }

        dijkstra(N);
        System.out.println(sec[K]);
    }

    public static void dijkstra(int N) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(N, 0));
        sec[N] = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int index = node.getN();

            if (visited[index])
                continue;

            visited[index] = true;

            for (int i = 0; i < graph.get(index).size(); i++) {
                int x = sec[index] + graph.get(index).get(i).getSec();
                if (x < sec[graph.get(index).get(i).getN()]) {
                    sec[graph.get(index).get(i).getN()] = x;
                    q.offer(new Node(graph.get(index).get(i).getN(), x));
                }
            }
        }
    }
}