[백준] 16928번 : 뱀과 사다리 게임

문제

16928번: 뱀과 사다리 게임

 

접근 방식

여러 풀이가 존재하는 문제 같지만 BFS를 사용해서 풀어봤다.

 

우선 문제에서는 10*10 맵이라고 했지만 그냥 100칸짜리 1차원 배열을 사용하는 것이

문제의 입력 양식을 처리하기가 편해서 맵과 방문 배열을 모두 1차원 배열을 사용했다.

 

평범한 BFS 문제와 방식은 비슷하지만 주사위의 눈만큼 이동하기 위해

방향 배열을 사용하는 것이 아닌 1 ~ 6까지 반복문을 돌아주었다.

 

사다리나 뱀은 무조건 타야 하기 때문에 이 부분만 주의하면서 탐색해 주고

방문 기록을 정수형 배열로 처리해 주사위를 굴린 횟수가 더 적은 경우에만

이동할 수 있게 해 주면 된다.

 

 

풀이

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[] map = new int[101];
		int[] isVisited = new int[101];
		Arrays.fill(isVisited, -1);

		int nm = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());

		while (nm-- > 0) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[x] = y;
		}

		Queue<Integer> q = new ArrayDeque<>();
		q.offer(1);
		isVisited[1] = 0;

		while (!q.isEmpty()) {
			int cur = q.poll();
			int move = isVisited[cur] + 1;

			for (int dice = 1; dice <= 6; dice++) {
				int next = cur + dice;

				if (next > 100) continue;

				if (map[next] != 0) {
					int x = map[next];

					if (isVisited[x] != -1 && isVisited[x] <= move) continue;

					isVisited[x] = move;
					q.offer(x);

					continue;
				}

				if (next == 100) {
					System.out.println(move);
					return;
				}

				if (isVisited[next] != -1 && isVisited[next] <= move) continue;

				isVisited[next] = move;
				q.offer(next);
			}
		}
	}
}