[백준 12851번] 숨바꼭질 2 - JAVA

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

12851번: 숨바꼭질 2

풀이

사용한 알고리즘: 우선순위큐를 사용한 다익스트라 알고리즘

 

풀이전략

제출하는데 계속해서 42~26% 사이에서 틀렸다는 결과가 나왔다.

거의 1시간 동안 고민을 한 끝에 제출해왔던 코드가 틀린 이유를 찾아냈는데

바로 방문여부를 결정하는 visited를 잘못된 위치에서 값 변경했기 때문이었다.

 

이미 방문한 위치는 다시 방문하지 않도록

우선순위 큐에 새로운 노드들을 push 하기 전에 현재 노드를 이미 방문했었다면

해당 노드로부터 파생되는 다른 노드로 다시 이동하지 않고 continue를 통해 반복을으로 돌아갔었다.

 

하지만 우리가 목표로 구하는 값은 목적지까지의 최소비용뿐만 아니라

해당 목적지를 최소비용으로 갈 수 있는 경우의 수도 구해야한다.

따라서 기존에 방문한 위치더라도 재방문할 수 있어야만 모든 경우의 수를 구할 수 있는 것이었다.

 

그래서 방문했던 노드들도 다시 방문할 수 있도록 continue를 없앴고,

노드를 push할 때 방문여부를 참으로 변강하지않고 pop할 때 참으로 변경하돠록 하였다.

 

제출코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{

    static class Node implements Comparable<Node>{
        int index;
        int cost;

        public Node(int index,int cost){
            this.index=index;
            this.cost=cost;
        }

        @Override
        public int compareTo(Node o) {
            if(this.cost<o.cost) return -1;
            else return 1;
        }
    }
    static int N,K;
    static boolean visited[] = new boolean[100001];
    static int leastCost=-1;
    static int resultCount=0;

    static void bfs(int start){
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start,0));

        while(!q.isEmpty()){
            Node now = q.poll();
            visited[now.index]=true;
            //System.out.println("index="+now.index+","+"cost="+now.cost);
            if(now.index==K){
                if(leastCost==-1) leastCost=now.cost;
                if(now.cost==leastCost) ++resultCount;
                //continue;
            }

            if(now.index-1<100001 && now.index-1>=0 && !visited[now.index-1]) q.offer(new Node(now.index-1,now.cost+1));
            if(now.index+1<100001 && !visited[now.index+1]) q.offer(new Node(now.index+1,now.cost+1));
            if(now.index*2<100001 && !visited[now.index*2]) q.offer(new Node(now.index*2,now.cost+1));
        }
    }
    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());

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

        bfs(N);
        bw.write(leastCost+"\n");
        bw.write(resultCount+"\n");
        bw.flush();
        bw.close();
    }
}