[백준] 16928 뱀과 사다리 게임 - 자바

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

16928번: 뱀과 사다리 게임

문제 풀이

이 문제는 bfs를 이용하는데 기존 그래프의 탐색을 약간 변형해서 접근해야 한다. 그래프에서 인접노드를 순회했다면 이 문제는 해당 좌표에서 이동할 수 있는 +1 ~ +6의 좌표를 순회하며 100까지 이동한다.

 

필자가 가장 헤맸던 부분은 뱀은 뒤로 움직이기 때문에 당연히 뱀의 위치는 방문하지 않는 방법을 택했다. 하지만 뱀을 이용할 때가 뱀을 이용하지 않을 때보다 더 적은 최소 횟수를 얻는 경우가 있다.

다음 예를 살펴보자

다음 그림과 같은 뱀과 사다리가 있다고 가정해보자.

먼저 사다리만을 이용했을 때이다

총 5회에 걸쳐 도착지점 100에 도달하게 된다.

 

다음은 뱀을 같이 이용했을 때이다

보다시피 뱀을 이용했을 때 21까지 빠르게 도착할 수 있다. 총 3회에 21에 도착한 반면 사다리만 이용했을 때는 4회를 걸쳐 도착하게 됐다.

 

따라서 결론은 최소 횟수로 도착지점에 도달하기 위해 뱀 또한 이용해야 한다는 것이다.

 

 

코드

package 백준;

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

public class b16928 {
    static int N, M, cnt;
    static boolean[] visited;
    static Map<Integer, Integer> snakeAndLadder; // 뱀과 사다리의 좌표

    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());

        visited = new boolean[101];
        snakeAndLadder = new HashMap<>();

        // 뱀과 사다리 등록
        for(int i=0; i<N+M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            snakeAndLadder.put(x, y);
        }

        bfs();
        System.out.println(cnt);
    }

    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visited[1] = true;

        while(!q.isEmpty()) {
            cnt++;
            for(int i=0,qSize=q.size(); i<qSize; i++) {
                int now = q.poll();

                for(int j=1; j<=6; j++) {		//주사위값 계산
                    int move = now + j;
                    if (move == 100) return; // 도착
                    if(move > 100 || visited[move]) continue;

                    visited[move] = true;

                    //뱀, 사다리를 만남
                    if(snakeAndLadder.containsKey(move)) {
                        move = snakeAndLadder.get(move);
                    }

                    q.add(move);
                }
            }
        }
    }
}

 

느낀점

사실 처음부터 뱀을 이용해야 할까? 많이 고민했지만 직접 샘플로 예시를 설정해 모든 상황을 고려했지만 뱀을 이용하지 않을 때가 가장 적은 횟수로 도달했기에 뱀의 좌표가 나오면 무시하는 로직을 설정했었다.

 

하지만 위와 같이 결론은 뱀을 이용해야 한다는 것이다. 물론 올바르고 효율적인 문법으로 코딩하는 것은 중요하지만 올바른 설계 방법 또한 매우 중요하다는 것을 다시 깨달았다