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

코드 힌트

1. 입력 처리
   • 사다리와 뱀의 개수를 입력받고, 각 사다리와 뱀의 시작 위치와 도착 위치를 배열 board에 저장합니다. 사다리와 뱀은 동일한 방식으로 처리됩니다.
2. 보드 초기화
   • board 배열에서 시작 위치에 도착 위치가 설정되지 않은 경우, 그 위치는 자기 자신으로 설정하여 기본 이동을 가능하게 합니다. 이는 뱀이나 사다리가 없는 경우입니다.
3. BFS 탐색
   • 큐를 사용하여 BFS(너비 우선 탐색) 방식으로 게임 보드를 탐색합니다. 큐에는 현재 위치와 그 위치에 도달하기 위한 이동 횟수를 저장합니다.
   • 주사위의 결과(1~6)를 기반으로 다음 위치를 계산하고, 해당 위치가 아직 방문하지 않았다면 큐에 추가합니다.
4. 종료 조건
   • 위치가 100에 도달했을 때, 이동 횟수를 비교하여 최소값을 업데이트합니다. BFS 특성상, 처음으로 100에 도달했을 때는 최소 이동 횟수입니다.
5. 결과 출력
   • 모든 탐색이 완료된 후, 최소 이동 횟수를 출력합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int[] board = new int[101]; // 1부터 100까지의 위치를 나타내는 배열
        
        int x = in.nextInt(); // 사다리의 개수 입력
        int y = in.nextInt(); // 뱀의 개수 입력
        in.nextLine(); // 줄바꿈 처리
        
        // 사다리와 뱀의 정보를 입력받아 board 배열에 저장
        for (int i = 0; i < x + y; i++) {
            int s = in.nextInt(); // 시작 위치
            int e = in.nextInt(); // 도착 위치
            board[s] = e; // 시작 위치에 도착 위치를 저장
            in.nextLine(); // 줄바꿈 처리
        }
        
        // board 배열에서 도착 위치가 설정되지 않은 경우, 자기 자신으로 설정
        for (int i = 0; i < 101; i++) {
            if (board[i] == 0) {
                board[i] = i; // 기본 이동
            }
        }
        
        int result = bfs(board); // BFS 탐색을 통해 결과를 얻음
        
        System.out.println(result); // 결과 출력
    }
    
    public static int bfs(int[] board) {
        Queue<int[]> q = new LinkedList<>(); // BFS를 위한 큐
        Set<Integer> set = new HashSet<>(); // 방문한 위치를 기록할 집합
        q.add(new int[] {1, 0}); // 시작 위치(1)와 이동 횟수(0)를 큐에 추가
        
        // BFS 탐색 시작
        while (!q.isEmpty()) {
            int[] arr = q.poll(); // 큐에서 현재 위치와 이동 횟수를 꺼냄
            int pos = arr[0]; // 현재 위치
            int count = arr[1]; // 이동 횟수
            
            // 100에 도달하면 이동 횟수를 반환
            if (pos == 100) {
                return count;
            }
            
            // 주사위를 굴린 결과를 기반으로 다음 위치를 탐색
            for (int i = 1; i <= 6; i++) { // 주사위 1~6의 결과
                // 이동 가능한 위치가 보드 내에 있고 방문하지 않았다면
                if (pos + i <= 100 && !set.contains(pos + i)) {
                    set.add(pos + i); // 현재 위치를 방문 처리
                    q.add(new int[] {board[pos + i], count + 1}); // board 배열에서 도착 위치로 이동
                }
            }
        }
        
        return -1; // 도달할 수 없는 경우 -1 반환
    }
}