백준 Q16928 - 뱀과 사다리 게임

문제 및 입출력

---

풀이

static Map<Integer, Integer> item = new HashMap<>();

뱀 또는 사다리를 타고 이동할 수 있는 좌표 (from -> to)를 보자마자 HashMap을 사용해야겠다고 생각했다.

가능한 모든 케이스에 대해서 1 -> 100 까지의 최적의 횟수로 이동할 수 있는 경우를 찾는 것이므로, 너비우선탐색을 적용하면 설계했던대로 풀 수 있을 것 같았다.

뱀과 사다리가 있는 지점을 특수한 경우라고 표현하겠다.

int next = cur + dice
현재 위치에서 주사위의 경우의 수 1~6를 각각 더한다

if(item.containsKey(next))
만약 이동하려는 지점이 특수한 경우를 담아놓은 해시맵에 포함된다면

queue.add(item.get(next))
큐에 해당 위치를 담고

visited[item.get(next)] = true
해당 지점을 방문 체크를 한다

특수한 지점이 아니라면 단순 next 값으로 대체하면 된다.

이때 count 각 스텝별 주사위를 굴린 횟수를 체크해야 하는데 여기서 초반에 오류가 발생하였다.

queue에서 현재 큐의 사이즈 만큼 가져온 다음에 이후 스텝을 처리해야 하는데, 큐의 사이즈를 정의하지 않고 단순히 while(!queue.isEmpty())조건 하나에 의존하여 하나의 스텝으로 쭉 이어지고, 주사위 굴린 횟수는 증가하지 않고 1에 머물렀다.

또한 종료 조건(cur==100) 을 정확히 명시하지 않아 프로그램이 종료되지 않는 문제가 발생했다.

---

최종 코드

public class Main {
	static Map<Integer, Integer> item = new HashMap<>();

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

		st = new StringTokenizer(br.readLine());
		int ladder = Integer.parseInt(st.nextToken());
		int snake = Integer.parseInt(st.nextToken());

		for (int i = 0; i < ladder + snake; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			item.put(from, to);
		}

		int result = bfs(1);
		System.out.println(result);
	}

	private static int bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[101];

		queue.add(start);
		visited[start] = true;

		int count = 0;

		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int cur = queue.poll();
				if (cur == 100) return count;

				for (int dice = 1; dice <= 6; dice++) {
					int next = cur + dice;
					if (next > 100) continue;
					if (!visited[next]) {
						if (item.containsKey(next)) {
							queue.add(item.get(next));
							visited[item.get(next)] = true;
						} else {
							queue.add(next);
							visited[next] = true;
						}
					}
				}
			}
			count++;
		}
		return count;
	}
}

---

풀이 후기

프로젝트를 진행하며 알고리즘을 병행하지 못하여 오랜만에 풀어보는 그래프 탐색 문제였다.
사실 그저께 구름톤 2월 모의 코테를 봤었는데 네 문제중 세번째 문제인 BFS문제를 수월하게.. 깔끔하게 풀지 못해서 복기할겸 해당 문제를 풀어봤다.
(이 문제도 깔끔하게 풀지 못했다)

유사한 문제중에 총 가구 단지의 수를 카운팅하고, 각 단지별로 속한 아파트 개수를 구하는 문제가 생각났다.
해당 문제는 2차원 배열에서 가구의 유무를 판단(0 or 1)하여 bfs의 진행 여부를 파악하면 되고, 위 문제는 모든 케이스에 대해 bfs를 진행해야 하므로 초기 세팅할때 느낌이 약간 다른것 같았다.

역시 꾸준히 알고리즘 문제를 풀며 감각을 유지해야 할 것 같다