문제 출처

단계별로 풀어보기 > 그래프와 순회 > 뱀과 사다리 게임
https://www.acmicpc.net/problem/16928

문제 설명

10x10 크기(100칸)의 보드가 있다.
주사위를 던져 1~6칸을 이동할 때, 이동한 칸에 사다리가 있는 경우 그 사다리와 이어져있는 칸으로 이동한다.
또한, 뱀이 있는 경우 그 뱀이 이어져있는 칸으로 이동한다.
사다리는 더 큰 칸으로, 뱀은 더 작은 칸으로 이동한다.

이 때, 주사위를 던져서 100번째 칸에 도착할 수 있는 최솟값을 구하시오.

접근 방법

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

public class 뱀과_사다리_게임 {

    public static int N,M;
    public static int[] arr = new int[101];
    public static boolean[] visited = new boolean[101];

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void bfs(int start) throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start,0});

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            if(cur[0] == 100){
                bw.write(String.valueOf(cur[1]));
                bw.flush();
                bw.close();
                return;
            }

            for(int i = 1; i < 7; i++){
                int next = cur[0] + i;
                if(next<=100){
                    if(arr[next]!=0){
                        next = arr[next];
                    }
                    if(!visited[next]){
                        visited[next] = true;
                        q.add(new int[]{next,cur[1]+1});
                    }
                }
            }
        }
    }

    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 + M; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x] = y;
        }

        bfs(1);


        br.close();

    }

}

알게된 점

처음 풀이할 땐, 2차원 배열로 풀려고 했으나 19 -> 20 으로 넘어갈 때 처리 부분이 까다로웠다.

arr에는 뱀과 사다리를 통해 이동하는 칸을 저장하고, visited는 방문 여부만 판단한다.

다시 한 번 풀어봐야겠다.

시간 복잡도는 O(보드 칸수 + 간선의 갯수(각 칸에서 이동 할 수 있는 경우 1~6))이다.

문제푼 흔적