[백준(Baekjoon)][자바(java)] 16928 : 뱀과 사다리 게임 / 그래프와 순회

 

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

16928번: 뱀과 사다리 게임

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	
	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()), m = Integer.parseInt(st.nextToken()), i;
		Map<Integer, Integer> map_ladder = new HashMap<>(), map_snake = new HashMap<>();
		for (i = 0; i < n; ++i) {
			st = new StringTokenizer(br.readLine());
			map_ladder.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			map_snake.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		br.close();

		final int start = 1, end = 100;

		Deque<int[]> queue = new ArrayDeque<>(); // pos, cnt
		queue.add(new int[]{start, 0});

		boolean[] visited = new boolean[end + 1];
		visited[start] = true;

		int cell[], pos_cur, pos_next, cnt_cur, cnt_next, answer = 0;
		loop:
		while (!queue.isEmpty()) {
			cell = queue.remove();
			pos_cur = cell[0];
			cnt_cur = cell[1];
			cnt_next = cnt_cur + 1;
			for (i = 6; i >= 1; --i) {
				pos_next = pos_cur + i;
				if (pos_next > end || visited[pos_next])
					continue;
				if (pos_next == end) {
					answer = cnt_next;
					break loop;
				}
				if (map_ladder.containsKey(pos_next))
					pos_next = map_ladder.get(pos_next);
				if (map_snake.containsKey(pos_next))
					pos_next = map_snake.get(pos_next);
				queue.add(new int[]{pos_next, cnt_next});
				visited[pos_next] = true;
			}
		}

		System.out.println(answer);
	}
}