[BOJ/Java] 16928. 뱀과 사다리 게임

[BOJ/Java] 16928. 뱀과 사다리 게임

16928번: 뱀과 사다리 게임

---

문제 해석

이 문제는 플레이어가 주사위를 굴려 100번 칸에 도달하려고 할 때, 사다리와 뱀을 이용하여 최소 몇 번의 주사위 굴림으로 도달할 수 있는지 계산하는 문제이다. 사다리는 위로 올라가는 효과가 있고, 뱀은 아래로 내려가는 효과가 있다. 각 칸에서 다음 도착지는 미리 정해져 있으며, 1번 칸에서 시작한다.

풀이 과정

1. 입력 처리: N(사다리 수)과 M(뱀 수)을 입력받고, 해당 정보를 배열 map에 저장한다. map[i]는 i번 칸에서 도달할 수 있는 칸의 번호를 의미한다.
2. BFS 초기화 및 실행: 1번 칸에서 시작하여 주사위를 굴리는 모든 경우의 수를 고려하여 BFS를 실행한다.
3. 칸 이동 처리: 1부터 6까지 주사위를 굴려 이동 가능한 칸을 계산하고, 사다리나 뱀을 통해 바로 이동할 수 있는 경우를 처리한다. 이동 시 이미 방문한 칸은 건너뛴다.
4. 최소 이동 횟수 계산: 100번 칸에 도달하는 최소 이동 횟수를 계산한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No16928;

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

public class Main {
	private static int N; // 사다리의 수
	private static int M; // 뱀의 수
	private static int ans = Integer.MAX_VALUE; // 최소 이동 횟수
	private static int[] map; // 칸에서 도착할 수 있는 다른 칸을 저장하는 배열
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[106]; // 게임 판의 크기를 고려하여 배열 크기 설정
		for (int i = 0; i < N + M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			map[u] = v; // 사다리나 뱀의 시작과 끝 지점을 매핑
		}
		
		bfs(); // BFS를 이용한 탐색 시작
		sb.append(ans); // 결과 저장
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private static void bfs() {
		Queue<Info> q = new PriorityQueue<>();
		q.offer(new Info(1, 0)); // 1번 칸에서 시작
		boolean[] v = new boolean[106]; // 방문 배열
		v[1] = true; // 1번 칸 방문 처리
		
		while(!q.isEmpty()) {
			Info info = q.poll();
			
			if (info.count >= ans) return; // 이미 최소 횟수보다 많은 경우 종료
			
			if (info.now + 6 >= 100) {
				ans = Math.min(ans, info.count + 1); // 100번 칸에 도착할 수 있는 경우
				continue;
			}
			
			for (int i = 6; i >= 1; i--) {
				int next = info.now + i;
				if (next > 100 || v[next]) continue; // 범위를 벗어나거나 이미 방문한 경우
				if (map[next] != 0) {
					if (!v[map[next]]) {
						v[map[next]] = true;
						q.offer(new Info(map[next], info.count + 1)); // 사다리나 뱀을 타고 이동
					}
				} else {
					v[next] = true;
					q.offer(new Info(next, info.count + 1)); // 일반적인 이동
				}
			}
		}
	}
	
	static class Info implements Comparable<Info> {
		int now, count;
		public Info(int now, int count) {
			this.now = now;
			this.count = count;
		}
		@Override
		public int compareTo(Info o) {
			if (this.count == o.count) return o.now - this.now;
			return this.count - o.count;
		}
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 BFS 실행 시 각 칸에 대해 최대 6개의 주사위 결과를 고려하여 탐색을 진행하므로, 최대 100칸 * 6의 경우를 고려해야 하므로 O(600) 정도로 추정할 수 있다. 각 칸의 이동이 최대 한 번씩만 발생하기 때문에 효율적인 처리가 가능하다.

느낀점

이 문제를 통해 복잡한 이동 규칙을 가진 상황에서 BFS를 활용하여 최적의 해를 찾는 방법을 실습할 수 있었다. 또한, 우선순위 큐를 사용하여 탐색의 우선순위를 관리하는 방법도 이해할 수 있었다. 이는 다양한 시뮬레이션 및 경로 탐색 문제에 적용할 수 있는 중요한 기술이다.