[BOJ 16928] 뱀과 사다리 게임 (Java)

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

16928번: 뱀과 사다리 게임

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BOJ_16928 {
	static int N, M;
	static int answer=Integer.MAX_VALUE;
	static int[] marks=new int[101];
	static boolean[] check;
	static Map<Integer, Integer> ladders=new HashMap<>();
	static Map<Integer, Integer> snakes=new HashMap<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		for (int i=0; i<N; i++) {
			 st=new StringTokenizer(br.readLine());
			 int x=Integer.parseInt(st.nextToken());
			 int y=Integer.parseInt(st.nextToken());
			 marks[x]=1;
			 ladders.put(x, y);
		}
		for (int i=0; i<M; i++) {
			 st=new StringTokenizer(br.readLine());
			 int x=Integer.parseInt(st.nextToken());
			 int y=Integer.parseInt(st.nextToken());
			 marks[x]=2;
			 snakes.put(x, y);
		}
		bfs();
		System.out.println(answer);

	}
	private static void bfs() {
		check=new boolean[101];
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {1, 0});
		check[1]=true;
		while (!q.isEmpty()) {
			int x=q.peek()[0];
			int dist=q.peek()[1];
			q.poll();
			for (int d=1; d<=6; d++) {
				int nx=x+d;
				if (nx>=1 && nx<=100 && !check[nx]) {
					if (nx==100) {
						answer=Math.min(answer, dist+1);
						return;
					}
					check[nx]=true;
					if (marks[nx]==1) {
						int dest=ladders.get(nx);
						check[dest]=true;
						q.add(new int[] {dest, dist+1});
					}
					else if (marks[nx]==2) {
						int dest=snakes.get(nx);
						check[dest]=true;
						q.add(new int[] {dest, dist+1});
					}
					else {
						q.add(new int[] {nx, dist+1});
					}
				}
			}
		}
	}

}

전형적인 bfs 문제.. 이나.. 다른 분들의 효율성 좋은 코드에서 많이 배워간다.(https://100100e.tistory.com/194)

백준(BOJ) 16928번 뱀과 사다리 게임

이 분의 코드도 BFS를 이용했으나, los 배열에 사다리와 뱀의 위치를 표시해준다. 인덱스가 시작 위치가 되고, 인덱스에 대한 값이 종료 위치가 된다.

쭉 BFS 탐색을 하면서, nx 노드가 뱀이나 사다리의 시작 위치라면(los[nx]!=0), 종료 위치로 그 값을 바꿔준다.

또한 큐에서 dist 값을 따로 가지고 다닐 필요가 없이, dist 배열을 이용하여 방문 여부와 그 위치까지 도달하는데 필요한 시간을 모두 저장할 수 있다. dist[nx]=dist[x]+1 가 되고, 미방문 역시 dist배열이 -1 일 때로 간주해주면 된다.