2023-04-03 BOJ 16928

문제 풀이 방식

• 최소거리니까 BFS

문제 풀이 (Java)

import java.io.*;  
import java.util.*;  
  
public class boj16928{  
    static int[] map;  
    static int N, M;  
    public static void main(String[] args) throws Exception{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        map = new int[100];  
  
        //사다리   
N = Integer.parseInt(st.nextToken());  
        //뱀   
M = Integer.parseInt(st.nextToken());  
        for(int i = 0 ; i < N ; i++) {  
            st = new StringTokenizer(br.readLine());  
            int start = Integer.parseInt(st.nextToken());  
            int end = Integer.parseInt(st.nextToken());  
  
            map[start - 1] = end - 1;  
        }  
  
        for(int i = 0 ; i < M ; i++) {  
            st = new StringTokenizer(br.readLine());  
            int start = Integer.parseInt(st.nextToken());  
            int end = Integer.parseInt(st.nextToken());  
  
            map[start - 1] = end - 1;  
        }  
  
        bfs();  
  
    }  
    private static void bfs() {  
        Queue<Integer> queue = new LinkedList<Integer>();  
        boolean[] visited = new boolean[100];  
  
        queue.offer(0);  
        visited[0] = true;  
        int time = 0;  
        while(! queue.isEmpty()) {  
            time ++;  
            int size = queue.size();  
            for(int i = 0 ; i < size ; i++) {  
                int cur = queue.poll();  
                for(int plus = 1 ; plus <= 6 ; plus ++) {  
                    int nx = cur + plus;  
  
                    if(0 > nx || nx > 99 || visited[nx]) continue;  
                    // 목적지 도착 할때   
if(nx == 99) {  
                        queue.clear();  
                        System.out.println(time);  
                        return;  
                    }  
                    // 사다리나 뱀이 없음   
if(map[nx] == 0) {  
                        queue.add(nx);  
                        visited[nx] = true;  
  
                    }  
                    else {  
                        if(visited[map[nx]]) continue;  
                        queue.add(map[nx]);  
                        visited[map[nx]] = true;  
  
                    }  
                }  
            }  
        }  
    }  
}