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

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

 

package graph;

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

public class Graph16928 {

    static int N;

    static int M;

    static int[][] map = new int[101][1];

    static boolean[] visit = new boolean[101];

    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());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            map[x][0] = y;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            map[u][0] = v;
        }


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

    private static int bfs() {
        int cnt = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visit[1] = true;

        while (!queue.isEmpty()) {

            cnt++;
            for (int j = 0, size = queue.size(); j < size; j++) {

                int temp = queue.poll();

                for (int i = 1; i < 7; i++) {
                    int value=0;
                    if (map[temp + i][0] != 0 && !visit[temp + i]) {
                        value = map[temp + i][0];
                        queue.add(map[temp + i][0]);
                    } else {
                        if (temp + i <= 100 && !visit[temp+i]) {
                            value = temp + i;
                            queue.add(temp + i);
                        }
                    }

                    visit[temp]=true;
                    if (value == 100) {
                        return cnt;
                    }
                }
            }

        }
        return 0;
    }
}

 

매우 이지한 문제였다. 골드5가 아니라 실버5문제인듯.. 

map[101][1] 를 선언하다. 이떄 저 1은 N과 M의 입력을 넣기 위함이다. 즉 N으로 봤을때 입력이 2, 10이면 map[2][0]=10으로 넣으면 된다. 반대로 M으로 봤을 때, 입력이 15, 5이면 map[15][0]=5이다. 이 상태로 쭉 설정해놓고 Queue를 이용해 주사위가 6개 방향이 나오니깐 그 모든 경우의수를 따져가면서 계산하면된다. 이때 메모리 초과가 발생할 수 있으므로 visit 배열을 활용하여 방문한 곳은 넣지 말아야된다.