16928번

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

16928번: 뱀과 사다리 게임

이 문제는 1에서 시작해서 100에 도달하는 방법을 주사위가 나오는 눈의 수로 했을 때 최단으로 가는 걸 구하는 문제다.

여기서 신경 쓸것은 뱀과 사다리이다. 기본적으로는 주사위의 눈의 수만큼 이동하지만 사다리나 뱀을 만나면 그 위치로 이동하게 된다.

처음 이 문제를 풀때 헷갈리는 부분이 있었다. 시작점을 1로하고 수를 셀 때, 뱀이나 사다리에 도달하면 뱀과 사다리의 시작점과 종착점을 둘다 큐에 넣어야하는지 종착점만을 넣어야하는지 헷갈렸다.

 

결론은 종착점만을 큐에 넣는 것이다. 최소 횟수이기 때문에 사다리와 뱀의 종착점을 큐에 넣는다.

나머지는 BFS구현 로직과 같다.

그리고 또 실수 한 부분이 있는데, 시작지점이었다. 

 

문제에는 아래와 같은 얘기가 나와있는데

"1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다."

나는 이 문장을 읽고 1번이 시작이 아닐 수도있다고 이상한 해석을 해버려서....bfs를 1부터 6 중에 하나의 경우로 시작하는 코드를 짜버렸다....

문제에는 아래와 같은 얘기가 있었는데 보질 못했다...바보인가...

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

 

그래서 이 부분을 수정해서 1부터 시작하여 내부 카운팅 방법으로 코드를 수정했고, 큐에 주사위의 눈이 1부터 6인 경우를 넣는 코드로 구현하고, 만약 도착한 지점이 사다리나 뱀이라면 옮겨지는 지점으로 큐에 집어넣는 처리를 해주었다.

 

그래서 정답 코드는 아래와 같다.

package backjoon.b16928;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class b16928 {
    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 M = Integer.parseInt(st.nextToken());
        Graph g = new Graph();
        for(int i=0;i<N+M; i++){
            st=new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            g.addEdge(u,v);
        }
        int min=g.bfs();
        System.out.println(min);
    }
}
class Graph{
    HashMap<Integer,Integer> adj;
    int[] dx = {1,2,3,4,5,6};
    Queue<target> queue;
    boolean[] visit = new boolean[101];
    public Graph() {
        adj = new HashMap<>();
        queue=new LinkedList<>();
    }
    public void addEdge(int u, int v){
        adj.put(u,v);
    }
    public int bfs(){
        visit[1]=true;
        queue.add(new target(1,0));
        while (!queue.isEmpty()){
            target tmp = queue.poll();

            for(int i=0; i<6; i++){
                int x = tmp.x+dx[i];
                if(x<=100 && !visit[x]){
                    if(adj.containsKey(x)){
//                        queue.add(new target(adj.get(x),tmp.cnt));
                        visit[adj.get(x)]=true;
                        x=adj.get(x);
                    }
                    if(x==100){
                        return tmp.cnt+1;
                    }
                    queue.add(new target(x,tmp.cnt+1));
                    visit[x]=true;
                }
            }
        }
        return -1;
    }
}
class target{
    int x;
    int cnt;

    public target(int x, int cnt) {
        this.x = x;
        this.cnt = cnt;
    }
}