BOJ_G5_16928

📁 [G5_16928] 뱀과 사다리 게임

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


public class Main {
	static int N, M, res;
	static int[] map;
	static int[] cnt;
	static boolean[] v;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// **** input start ****
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[101];
		v = new boolean[101];
		cnt = new int[101];

		for (int i = 0; i < N + M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			// 어차피 사다리 , 뱀 이동하는 것은 같다
			map[start] = end;
		}
		// **** input end ****

		bfs();

		System.out.println(res);

	} // main end

	// bfs
	static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		// 카운팅, 방문처리
		cnt[1] = 0;
		v[1] = true;

		while(!queue.isEmpty()) {
			int cur = queue.poll();

			if(cur == 100) {
				res = cnt[cur];
				break;
			}

			// 주사위 던지기
			for(int i=1; i<=6; i++) {
				int next = cur + i;

				// 100을 넘거나 이미 방문한 경우 통과
				if(next > 100 || v[next]) continue;

				// 이동할 거리가 있는 경우 ( 사다리 아니면 뱀 )
				if(map[next] != 0) {
					// 도착하는 곳이 방문하지 않은 경우
					if(!v[map[next]]) {
						// 방문처리
						v[map[next]] = true;
						// 카운팅
						cnt[map[next]] = cnt[cur] +1;
						queue.add(map[next]);
					}
				}
				// 이동할 거리가 없는 경우
				else {
					// 방문처리
					v[next] = true;
					cnt[next] = cnt[cur] + 1;
					queue.add(next);
				}
			}
		}
	}
} // class end

🤔 나의 생각

처음에 뱀과 만나는 것은 무조건 안된다 라고 생각해서 dfs를 통해 뱀을 만나면 돌아가는 형식으로 했는데 답이 안나오길래 찾아보니 뱀이 거쳐서도 최소 경로가 존재해서 틀린 것이였다..
한마디로 문제 접근이 잘못된..

그래서 찾아보니 bfs와 dp를 활용해 풀어냈다. 카운팅을 배열로 하여 저장해주는 것이 나는 생각하지 못한 방법이다..

• 전체 좌표, 방문처리 배열, 카운팅 배열을 생성한다.
• bfs를 활용하여 queue에서 poll 한 것이 100이 되면 끝낸다.
• 주사위를 다 던지면서 100을 넘거나 방문한 경우 통과
• 만약 사다리나 뱀이 있는 곳일 경우 다음 가는 곳에 방문하지 않았으면 다음 가는 곳을 queue에 add 한다.
• 만약 이동할 곳이 없는 경우 계속 더해준다. 카운팅배열을 갱신해 주면서 ( 한 번 바뀔때마다 1추가 )

뭔가 자꾸 문제를 어렵게 생각하는 것 같다… 천천히 쉽게 생각하자 !