[JAVA/16928번] 뱀과 사다리 게임

문제

입력 및 출력

풀이

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

class Main {
    public static int[] map = new int[101];
    public static boolean[] visited = new boolean[101];

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 사다리의 수 N, 뱀의 수 M
        String[] temp = br.readLine().split(" ");
        int N = Integer.parseInt(temp[0]);
        int M = Integer.parseInt(temp[1]);

        // 사다리의 정보와 뱀의 정보
        for (int i = 0; i < N + M; i++) {
            temp = br.readLine().split(" ");
            int startPos = Integer.parseInt(temp[0]); //출발지점 
            int endPos = Integer.parseInt(temp[1]); //도착지점

            map[startPos] = endPos;
        }

        // bfs 함수 호출
        bfs();
    }

    public static void bfs() {
        // Node타입을 갖는 큐 선언
        Queue < Node > queue = new LinkedList < > ();

        // queue에 Node를 넣고, 방문처리를 한다.
        queue.add(new Node(1, 0));
        visited[1] = true;

        while (!queue.isEmpty()) {
            Node curPos = queue.poll();

            if (curPos.pos == 100) {
                System.out.println(curPos.count);
                return;
            }

            // 주사위의 면은 총 6개이기 때문에 6만큼 반복수행
            for (int i = 1; i <= 6; i++) {
                if (curPos.pos + i <= 100) {
                    if (map[curPos.pos + i] == 0 && !visited[curPos.pos + i]) {
                        // 범위안에 들고 방문하지 않은 곳일경우
                        queue.add(new Node(curPos.pos + i, curPos.count + 1));
                        visited[curPos.pos + i] = true;
                    } else if (map[curPos.pos + i] != 0 && !visited[curPos.pos + i]) {
                        queue.add(new Node(map[curPos.pos + i], curPos.count + 1));
                        visited[map[curPos.pos + i]] = true;
                    }
                }
            }
        }
    }
}

class Node {
    int pos, count;
    public Node(int pos, int count) {
        this.pos = pos;
        this.count = count;
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법
데스나이트와 유사한 문제로 너비우선탐색을 통해 문제를 해결할 수 있었다. 거의 유사하나, 이번 문제는 뱀이나 사다리를 통해 이동을 할 수 있는 변수가 있다는 점이 다르다.

Node타입을 갖는 큐를 선언하였다. 다음으로 큐에 출발지 노드를 생성하고 해당 인덱스를 방문완료 표시하였다.

다음으로, 큐가 비어있지 않을 경우 반복문을 수행하도록 설정하고 큐에 가장 앞에 있는 원소를 추출한 뒤 그 원소가 100일 경우 해당 원소의 이동횟수를 화면에 출력했다.

주사위를 던져서 나올 수 있는 경우의 수는 총 6개이기 때문에 반복문을 6회 수행하였다. 다음 조건문으로 현재 위치에서 i를 더한 값이 100보다 크지 않을 경우 두 가지 분기로 나누어 수행했는데 첫 번째는 사다리나 뱀이 없는 경우이고, 두 번째는 사다리나 뱀이 있는 경우로 나누어 수행했다.