[알고리즘] 백준 13549 숨바꼭질 3 -bfs- 자바

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

 

 

 

 

 

 

 

BFS문제로 이전에 푼 숨바꼭질 문제와 비슷하나 순간이동시 0초가 걸리게 바꼈습니다.

youngest-programming.tistory.com/379

[알고리즘] 백준 1697 숨바꼭질 -bfs, dfs- 자바 코틀린

0초로 바꼈을 뿐인데 이전 코드에서 꽤 많이 변경해야했습니다.

 

풀이 방법을 간략히 설명하면

 

1. 우선순위 큐로 이동횟수 적은 순으로 큐에 담아지게 하였습니다. 또한 0초가 걸리는 순간이동을 먼저 탐색하게 했습니다.

 

2. 기존에는 다 1초씩 걸려서 여기까지 오는데 걸리는 시간초를 담는 map[]이란 Int 배열을 써서 0인 경우에만 아직 방문안한 경우이므로 방문하고 동생이 있는 위치의 map을 이용해 결과값을 도출했는데 여기서는 순간이동이 다른 시간초인 0초로 바꼈으므로 isVisited boolean형 타입 배열로 방문처리를 해결하고 Point라는 클래스를 추가적으로 만들었습니다.

 

3. 그 후 bfs 탐색을 돌리면 되는데 주의 할점은 isVisited[point.pos] = true; 를 큐에 넣을때가 아닌 뺄때 해야 시간초가 어긋안난다는 점 입니다. 

 

여담으로..

5 18 이면 5-1*2*2 로 1이 맞는데 5*2*2-1-1로 2초라 생각해서 계속 왜 틀렸지하고 삽질을 했습니다.

 

 

 

[Java]

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {
    private static int N; //수빈이 위치
    private static int K; //동생 위치
    private static boolean[] isVisited = new boolean[100001];
    private static int answer = Integer.MAX_VALUE;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        bfs();
        System.out.println(answer);
    }

    static void bfs() {
        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.offer(new Point(N, 0));
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            isVisited[point.pos] = true; //3가지케이스에 큐에 offer한다음에 방문처리하면 우선순위때문에 최소거리 바뀌는 경우 발생함
            if (point.pos == K) {
                answer = point.count;
            }
            if (point.pos * 2 <= 100000 && !isVisited[point.pos * 2]) { // 0초 순간이동
                queue.offer(new Point(point.pos * 2, point.count));
            }
            if (point.pos + 1 <= 100000 && !isVisited[point.pos + 1]) { //1초 한칸우측
                queue.offer(new Point(point.pos + 1, point.count + 1));
            }
            if (point.pos - 1 >= 0 && !isVisited[point.pos - 1]) { //1초 한칸좌측
                queue.offer(new Point(point.pos - 1, point.count + 1));
            }
        }
    }

    private static class Point implements Comparable<Point>{
        int pos;
        int count;

        public Point(int pos, int count) {
            this.pos = pos;
            this.count = count;
        }

        @Override
        public int compareTo(Point o) {
            return count - o.count;
        }
    }

}

 

 

 

 

추가로 숨바꼭질 2 도 있는데 

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

풀이를 기록합니다.

import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    private static int[] map = new int[100001];
    private static boolean[] isVisited = new boolean[100001];
    private static int K;
    private static int lastCnt = Integer.MAX_VALUE;
    private static int answerCount = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //누나 위치
        K = sc.nextInt(); //동생 위치
        bfs(N);
        System.out.println(lastCnt);
        System.out.println(answerCount);
    }

    private static void bfs(int n) {
        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(n, 0));
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int pos = point.pos;
            int count = point.count;
            isVisited[pos] = true;
            if (pos == K && lastCnt >= count) {
                lastCnt = count;
                answerCount++;
                continue;
            }
            if (pos * 2 < 100001 && !isVisited[pos * 2]) {
                queue.offer(new Point(pos * 2, count + 1));
            }
            if (pos + 1 < 100001 && !isVisited[pos + 1]) {
                queue.offer(new Point(pos + 1, count + 1));
            }
            if (pos - 1 >=0 && !isVisited[pos - 1]) {
                queue.offer(new Point(pos - 1, count + 1));
            }
        }
    }

    static class Point implements Comparable<Point> {
        int pos;
        int count;

        public Point(int pos, int count) {
            this.pos = pos;
            this.count = count;
        }

        @Override
        public int compareTo(Point o) {
            return count - o.count;
        }
    }
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!