[Algorithm/Java] 백준 16928번 - 뱀과 사다리 게임 🐍🪜🎲
https://www.acmicpc.net/problem/16928
📌 문제
문제 유형
- 그래프
문제 설명
- 뱀과 사다리가 있는 1~100번 게임판에서 주사위를 굴려 가장 빨리 100번 칸에 도착하는 최소 횟수를 구하는 문제
- 사다리를 만나면 위로 올라가고, 뱀을 만나면 아래로 떨어짐
입력
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.
다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.
1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.
3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17
출력
100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.
3
🔍 문제 풀이
[Main] 함수
- Board를 1부터 100까지 i로 초기화
- 뱀과 사다리 칸으로 Board 대체
- Bfs(1) 호출 (1번칸부터 시작하므로)
[Bfs 함수]
- 큐에다가 현재 위치 넣고 현재 위치 방문처리
- 그리고 그 큐를 꺼낸다음 주사위 굴리기
- 즉, 다음위치 = 현재위치 + 주사위 굴린 위치
- 100 넘으면 continue
- 만약 방문하지 않은 칸이라면, dist 배열에 횟수 저장 후 다음 위치로 이동
📌 헷갈린 점
move = board[next]
가 필요할까?
처음에는 int move = board[next];
를 쓰지 않고 그냥 next를 그대로 사용했지만,
사다리나 뱀을 타는 경우 최종 도착 위치는 board[next]
로 이동해야 하기 때문에,
해당 코드를 반드시 추가해줘야 정확한 경로 계산이 가능하다는 걸 알게 됨
안 쓰면 사다리나 뱀 정보를 무시하고 단순히 주사위로만 움직이게 됨
visited[]
배열만으로 충분할까?
처음엔 visited[]
하나로도 충분하다고 생각했지만,
최소 주사위 횟수를 구하려면 각 칸까지의 거리를 따로 기록해야 함
따라서,
dist[]
배열을 사용하여 각 칸에 도달했을 때의 최소 주사위 횟수(거리)를 기록하도록 함
dist[i] = dist[current] + 1; // i번 칸까지 몇 번 만에 도달했는지 기록
BFS에서 사다리로 도착한 칸은 다시 안 봐도 되는 이유
move
가 이미 visited == true
일 경우,
사다리 타고 도달한 칸을 탐색 못하는 게 아닐까 걱정했지만,
BFS는 먼저 도달한 경로가 항상 최단이므로 이미 방문한 칸은 다시 탐색할 필요 없다.
💻 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int[] board;
static boolean[] visited;
static int[] dist;
static int bfs(int start){
Deque<Integer> dq = new ArrayDeque<>();
dq.offer(start);
visited[start] = true;
while (!dq.isEmpty()){
int current = dq.poll();
for(int i=1; i<=6; i++){
int next = current + i;
if(next > 100) continue;
int move = board[next]; // 주의
if (!visited[move]) {
dq.offer(move);
visited[move] = true;
dist[move] = dist[current] + 1;
}
}
}
return dist[100];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 사다리 수
int m = Integer.parseInt(st.nextToken()); // 뱀의 수
board = new int[101];
visited = new boolean[101];
dist = new int[101];
// board 초기화
for(int i=1; i<=100; i++){
board[i] = i;
}
// board 칸 -> 사다리 칸으로 대체
while(n -- > 0){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
board[x] = y;
}
while(m -- > 0){
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
board[u] = v;
}
int result = bfs(1); // 1번칸부터 시작
System.out.println(result);
}
}
댓글남기기