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

16928 문제 링크

---

https://www.acmicpc.net/problem/16928

 

문제 설명

---

 

입출력

---

 

코드

---

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static Queue<Integer> queue = new LinkedList<>();
    static Integer[] visit;
    static HashMap<Integer, Integer> map = new HashMap<>();
    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());
        visit = new Integer[101];
        
        for(int i = 0; i < N + M; i++) {
            st = new StringTokenizer(br.readLine());
            map.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        bfs(); // 1 출발
        bw.write(String.valueOf(visit[100]));
        bw.flush();
    }
    
    private static void bfs() {
        queue.offer(1);
        visit[1] = 0;
        
        while(!queue.isEmpty()) {
            int current = queue.poll();
            for(int i = 1; i <= 6; i++) {
                int next = current + i;
                if (next <= 100 && visit[next] == null) {
                    visit[next] = visit[current] + 1;
                    if (map.containsKey(next)) {
                        queue.offer(map.get(next));
                        if(visit[map.get(next)] == null) {
                            visit[map.get(next)] = visit[next];    
                        }
                    } else {
                        queue.offer(next);
                    }
                }
            }
        }
    }
}

 

알고리즘 설명

---

해당 문제는 골드 5레벨이라고 하기에는 풀이가 생각보다 쉬운 문제라고 생각합니다. 기존 bfs문제에 일차원 배열로 진행이 되는 구조이고, 1-base-position이기 때문에 101크기의 Integer 배열을 만들고 null값인 경우에만 조건에 맞추어 배열의 값을 세팅해주는 간단한 문제입니다. 사다리와 뱀의 차이는 그저 값의 증가/감소의 차이입니다. 배열을 방문한경우의 조건을 넣어주는 것이 핵심이라고 생각합니다.

 

bfs가 큐의 자료구조를 이용하는 만큼 어느정도는 정형화된 풀이가 가능하다고 생각합니다.

 

코드 해석

---

N과 M을 입력받고 N+M만큼 해시맵에 사다리와 뱀의 입력값을 키: 밸류로 받습니다. visit배열에는 101만큼 크기를 설정하고, bfs로 최소 이동 횟수를 계산합니다. 이후 visit[100]을 출력합니다.