[백준] 16928 뱀과 사다리 게임 [자바]

 

 

---

https://www.acmicpc.net/board/view/80099

글 읽기 - 해당 문제를 dp로 풀수 없는 이유

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static int[] rope;
	static int[] graph;
 	public static void main(String arg[]) 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());
 		rope = new int[101];
 		graph = new int[101];
 		for(int i = 0; i < N; i++) {
 			st = new StringTokenizer(br.readLine(), " ");
 			rope[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
 		}
 		for(int i = 0; i < M; i++) {
 			st = new StringTokenizer(br.readLine(), " ");
 			rope[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
 		}
 		bfs();
 		System.out.println(graph[100]);
 	}
 	static void bfs() {
 		LinkedList<Integer> que = new LinkedList<>();
 		que.add(1);
 		graph[1] = 0;
 		while(!que.isEmpty()) {
 			int temp = que.poll();
 			for(int i = 1; i <= 6; i++) {
 				if(temp+i <= 100) {
 					if(rope[temp+i] != 0) {
 						if(graph[rope[temp+i]] == 0 || graph[rope[temp+i]] > graph[temp] + 1) {
 							graph[rope[temp+i]] = graph[temp]+1;
 							que.add(rope[temp+i]);
 						}
 					}
 					else {
 						if(graph[temp+i] == 0 || graph[temp+i] > graph[temp] + 1) {
 							graph[temp+i] = graph[temp]+1;
 							que.add(temp+i);
 						}
 					}
 				}
 			}
 		}
 	}
}