백준 16928525 - 뱀과 사다리 게임

Java

16928 번 - 뱀과 사다리 게임

문제

접근 방법

100까지 도착하는 최단 거리는 BFS로 해결 할 수 있다.
사다리나, 뱀을 타는 것은 배열로 나타내었다.

코드

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

public class Main {
	static int n, m, result;
	static int[] move;
	static int[] dist;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	move = new int[101];
		// 사다리
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		move[stoi(stk.nextToken())] = stoi(stk.nextToken());
    	}
		// 뱀
    	for(int j = 0; j < m; j++) {
    		stk = new StringTokenizer(br.readLine());
    		move[stoi(stk.nextToken())] = stoi(stk.nextToken());
    	}

    	dist = new int[101];
    	Arrays.fill(dist, -1);	// -1은 아직 방문하지 않은 상태

    	Queue<Integer> queue = new LinkedList<Integer>();
    	queue.add(1);
    	dist[1] = 0;
    	int curN, nextN;
    	while(!queue.isEmpty()) {
    		curN = queue.poll();

    		if(dist[100] != -1) {
    			break;
    		}
    		for(int i = 1; i <= 6; i++) {
    			nextN = curN + i;
    			if(nextN <= 100) {
					// 뱀이나 사다리를 탈 수 있을 때
	    			if(move[nextN] != 0) {
	    				nextN = move[nextN];	// 강제로 이동한다.
	    			}
					// 처음 방문한 곳이면
	    			if(dist[nextN] == -1) {
	    				dist[nextN] = dist[curN] + 1;
	    				queue.add(nextN);
	    			}
    			}
    		}
    	}
    	System.out.println(dist[100]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점