BEAKJOON / 백준 - JAVA 16928번 뱀과 사다리 게임

2024.08.10기준 - 골드5

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 사다리와 뱀이 있을 때, 주사위를 이용하여 최소 몇 번만에 100에 도달할 수 있는지 출력하는 문제입니다.

 

1. 해당 칸에 도착했을 때, 이동되는 칸을 저장하는 배열을 생성했습니다.

// 해당 칸에 도착했을 때, 이동하는 좌표를 저장.
num = new int[101];
for (int i = 1; i < 101; i++) {
    num[i] = i;
}

 

2. 생성된 배열에 사다리와 뱀을 입력 시켜 수를 저장합니다.

int start, end;
while (n-- > 0) {
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken());
    end = Integer.parseInt(st.nextToken());

    num[start] = end;
}

while (m-- > 0) {
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken());
    end = Integer.parseInt(st.nextToken());

    num[start] = end;
}

 

3. 총 몇번의 주사위로 그 지점에 갈 수 있는지 저장하는 배열을 생성했습니다.

count = new int[101];

 

4. BFS 함수를 생성해 100번째 칸이 들어오면 return을 하여 정답을 출력하게 해줍니다.

private static int find() {
    Queue<Integer> qu = new LinkedList<>();
    qu.add(1);
    count[1] = 0;

    int now, next;
    while (true) {
        now = qu.poll();

        // 현재 위치에서 주사위를 굴려서 갈 수 있는 위치
        for (int i = 1; i <= 6; i++) {
            next = now + i;

            // 100보다 작으면서, 한 번도 가지 않았다면
            if (next <= 100 && count[num[next]] == 0) {
                count[num[next]] = count[now] + 1; // 현재 위치의 +1을 해서 저장.
                qu.add(num[next]);
            }
        }

        // 필요한건 100번째 수기 때문에 break
        if (count[100] != 0) {
            return count[100];
        }
    }
}

1. 주사위를 굴릴 때 마다 큐에 도착 지점을 넣어줍니다.
2. 첫 시작은 1로 시작이 고정되어 1부터 시작합니다.
3. while문에 들어와 시작지점에서 부터 총 1 ~ 6까지의 수를 참조합니다.
4. 참조된 수의 count는 시작지점보다 주사위를 한 번 더 던지기 때문에 +1로 저장을 해주면서 큐에 추가해줍니다.
5. 그렇게 반복되다가 count[100]에 값이 들어오면 필요한건 100번 째 칸만 있으면 되기 때문에 함수를 종료해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	static int[] num;
	static int[] count;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 사다리의 개수
		int m = Integer.parseInt(st.nextToken()); // 뱀의 개수
		
		// 해당 칸에 도착했을 때, 이동하는 좌표를 저장.
		num = new int[101];
		for (int i = 1; i < 101; i++) {
			num[i] = i;
		}
		
		int start, end;
		while (n-- > 0) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			
			num[start] = end;
		}
		
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			
			num[start] = end;
		}
		
		count = new int[101];
		bw.write(Integer.toString(find()));
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static int find() {
		Queue<Integer> qu = new LinkedList<>();
		qu.add(1);
		count[1] = 0;
		
		int now, next;
		while (true) {
			now = qu.poll();
			
			// 현재 위치에서 주사위를 굴려서 갈 수 있는 위치
			for (int i = 1; i <= 6; i++) {
				next = now + i;
				
				// 100보다 작으면서, 한 번도 가지 않았다면
				if (next <= 100 && count[num[next]] == 0) {
					count[num[next]] = count[now] + 1; // 현재 위치의 +1을 해서 저장.
					qu.add(num[next]);
				}
			}
			
			// 필요한건 100번째 수기 때문에 break
			if (count[100] != 0) {
				return count[100];
			}
		}
	}
}