[자바] 백준 16928번 뱀과 사다리 게임

저거 재미있는데 뱀과 사다리 게임. 어렸을 때 해본 기억이 있습니다. 

 

근데 이렇게 시간이 흐른 뒤 코딩문제로 만날 줄이야. 

 

뱀은 미끄러워서 내려가는 걸까요.

 

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

16928번: 뱀과 사다리 게임

 

<나의 풀이>

 

이동 후 특정 지점에 도착하는 문제들도 꽤 많이 만나본 것 같습니다. 

 

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

16953번: A → B

이 문제도 사실 크게 다를게 없어 보이고

 

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

13549번: 숨바꼭질 3

이 문제도 비슷한 유형인데 풀이 다익스트라로 풀었던 기억이 있네요. 

 

문제를 정의해보자면, '100까지 도달하는 최단 횟수를 구해라'가 되겠습니다.

 

한 번에 이동에 1~6까지 이동이 가능하며 사다리를 타면 올라 갈 수 있고, 뱀을 만나면 내려오게 됩니다. 뱀을 타거나 사다리를 타는데 이동 횟수를 소모하지는 않습니다. 

 

그렇다면 '뱀을 피해서만 갈 수 있지 않을까?' 라는 생각이 들어서 뱀의 입력값을 무시하려 했지만.. 뱀이 연속해서 6개의 칸에 존재한다면 무적권 뱀을 만나야 합니다. 

 

완전 탐색을 통해 최단거리를 확인해야 한다고 생각하여 BFS를 이용한 완전탐색을 선택하였습니다. 

 

BFS를 구현 할때 주의할 점은,  '이미 큐에 넣은 노드를 중복해서 넣지 말기 (메모리 초과의 원인)' 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {
    static int[] map;
    static boolean[] vist;
    private static class Node implements Comparable<Node>{
        int now;
        int count;
        Node(int now,int count){
            this.now = now;
            this.count = count;
        }
        @Override
        public int compareTo(Node o){
            if(this.count==o.count){
                return o.now-this.now;
            }
            return this.count - o.count;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int labber = Integer.parseInt(st.nextToken());
        int snake = Integer.parseInt(st.nextToken());
        map = new int[101];
        vist = new boolean[101];
        for(int i=0;i<labber;i++){
            st = new StringTokenizer(bf.readLine());
            map[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<snake;i++){
            st = new StringTokenizer(bf.readLine());
            map[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }
        System.out.println(BFS());
    }
    public static int BFS(){
        PriorityQueue<Node> que = new PriorityQueue<>();
        que.add(new Node(1,0));
        while(!que.isEmpty()){
            Node now = que.poll();
            if(vist[now.now]){
                continue; //^^
            }else{
                vist[now.now] =true;
            }
            //System.out.println(now.now);
            if(now.now==100){
                return now.count;
            }
            for(int i=1;i<=6;i++){
                if(now.now+i>100){
                    continue;
                }
                if(map[now.now+i] != 0 && !vist[map[now.now+i]]){
                    que.add(new Node(map[now.now+i], now.count+1));
                }else if(!vist[map[now.now+i]]){
                    que.add(new Node(now.now+i, now.count+1));
                }
            }
        }
        return 0;
    }
}

 

BFS를 구현하면서 저는 PQ를 이용하였는데, 'PQ를 이용하는 것이 과연 효율적일까'에 대한 질문을 받아서 생각을 해보도록 하겠습니다. 

 

이런 최단거리 문제에서 PQ를 선택한 이유는 횟수가 적은 케이스를  먼저 확인하고 싶어서 입니다. 근데 생각해 보면 Queue를 사용하더라도 자연스럽게 횟수가 적은 케이스를 먼저 확인할 수 있겠네요.

 

맞네..

 

PQ를 사용해야 할 때는 그럼 어떤 상황일까요.

 

1. 한 노드에 갈 수 있는 길이 여러가지이며 각 길들이 다른 가중치를 가질 때

 

2. 비교해야 하는 값이 BFS에서 의미하는 거리와 다른 값일 때

 

이 부분에 대해서 조금 더 구체적으로 정리하고 싶은데. 그 수업 시작해서..