자바 - 백준 16928 / 뱀과 사다리 게임

자바 - 백준 16928 / 뱀과 사다리 게임
골드5

구현 방법

제가 초반에 많은 틀린 이유는 크게 두가지가 있었는데요.
첫번째로 현재 위치에서 갈 수 있는 조건은 세가지 중 하나인데 여러 경우로 생각했습니다.
예를 들어 현재 위치에 사다리나 뱀이 연결되어 있다면 그것만 가능한데. 그거 외로 그냥 주사위를 돌려 갈 수 있다고 착각을 했습니다.


두번째로 깊이우선 탐색으로 했습니다. 해당으로 구현하면 시간초과가 납니다. 이유는 간단합니다.
깊이 우선으로 탐색할 경우 모든 경우를 전부 탐색해야 가장 최소값을 알 수 있기 때문입니다.


따라서 이 문제는 넓이 우선 탐색으로 구현해야 합니다. 이렇게 구현 한다면 최초로 나오는 100이 최솟값이 되기 때문입니다.
왜냐하면 같은 주사위를 굴린 횟수(== 같은 깊이)에 대한 위치를 비교하기 때문입니다.


bfs

1. 위치 저장 큐, 방문 배열를 생성하고 1번을 큐에 넣고 방문 체크를 해줍니다.
2. 큐에서 같은 깊이(== 같은 주사위 굴린 횟수)의 현재 위치 정보를 꺼냅니다.
3. 꺼낸 현재 위치를 바탕으로 다음 위치를 계산합니다. (1 ~ 6 차례로 더해줌)
   3-1. 다음 위치가 100인 경우 주사위 굴린 횟수를 리턴하고 종료.
   3-2. 다음 위치가 이미 방문한 경우라면 2번으로 돌아감.
   3-3. 다음 위치를 방문체크하고, 사다리인 경우, 뱀인 경우, 아무것도 아닌경우로 나누어서 큐에 넣고 2번으로 돌아갑니다.

코드

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

/**
 * 백준 16928
 * 뱀과 사다리 게임
 * 골드5
 * https://www.acmicpc.net/problem/16928
 */
public class Boj16928 {

    static int N; // 사다리 수
    static int M; // 뱀 수
    static int[] info; // 사다리, 뱀 정보
    static int[] mInfo; // 뱀 정보

    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());
        M = Integer.parseInt(st.nextToken());

        info = new int[101];

        for(int i = 0; i < N + M; i++) {
            st = new StringTokenizer(br.readLine());
            info[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

        System.out.println(bfs());
    }

    public static int bfs() {

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[101];
        q.add(1); // 현재 위치, 굴린 횟수
        visited[1] = true;
        int answer = 0;

        while(!q.isEmpty()) {
            int size = q.size();
            answer++;

            while(size > 0) {
                int cur = q.poll();
                for(int i = 1; i <= 6; i++) {
                    int next = cur + i;

                    if(next == 100) {
                        return answer;
                    }

                    if(next > 100 || visited[next])
                        continue;

                    visited[next] = true;
                    if(info[next] > 0) {
                        q.add(info[next]);
                    } else {
                        q.add(next);
                    }
                }
                size--;
            }
        }

        return answer;
    }
}