[백준] Q16928 뱀과 사다리 게임JAVA

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

16928번: 뱀과 사다리 게임

어릴 때 하던 단순 보드게임이다.

 

문제의 이해

주사위를 조작할 수 있다면 최소 몇 번 만에 도착점에 도착이 가능한가.

주사위 1~6까지 10*10 보드판(고정)

1~100 순서대로 적혀있다.

 1. i위치 4칸 > i+4 칸

 2. 100칸 넘어간다면 이동할 수 없다.  ( 딱 100칸에 도착해야한다.)

 3. 도착한 칸 사다리라면, 사다리를 타고 위로 올라간다.

 4. 뱀 칸이라면 뱀을 따라 내려간다.

 5. 1칸시작 100칸 도착.

 

접근 방법

보드판이지만, 1~100까지 적혀있는 일차원 배열로 보아도 무방하다.  => 1차원 배열 사용.
주사위를 던지는 차례에 따라 갈 수 있는 count를 세면서 목표지점에 도달할시 종료할 수 있는 
"최소 거리 또는 횟수" => BFS를 활용하자.
경우에 따라 dp[i] = i번째 도착 최소 횟수로 dp로 접근 할 수도 있을 것 같다.

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

public class Q16928 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        HashMap<Integer, Integer> info = new HashMap<Integer, Integer>();
        // L과 S의 정보를 확인하기 위해 Map에 포함시킨다.
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            info.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        for (int i = 0; i < S; i++) {
            st = new StringTokenizer(br.readLine());
            info.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        boolean[] visited = new boolean[101];
        int ans = -1;
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(1, 0));
        visited[1] = true;
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            // count를 통해 중복을 제거하고 
            // count에 따라 우선순위가 부여되기에 처음 도착한 100은 항상
            // 최소 횟수이다.
            if (cur.x == 100) {
                ans = cur.dist;
                break;
            }
            for (int i = 1; i <= 6; i++) {
                int nx = cur.x + i;
                if (nx <= 100 && !visited[nx]) {
                    visited[nx] = true;
                    if (info.containsKey(nx)) {
                        nx = info.get(nx);
                        visited[nx] = true;
                    }
                    queue.add(new Point(nx, cur.dist + 1));
                }
            }
        }
        System.out.println(ans);
    }

    static class Point {
        int x;
        int dist;

        Point(int x, int dist) {
            this.x = x;
            this.dist = dist;
        }
    }
}

문제 및 해결

글 작성 계기는 큰 틀에서의 로직은 맞았는데 "디테일" 이 부족했던 것 같다.

 

처음 문제 풀 때는 사다리 또는 뱀의 위치에 도착시 이후에 해당 번호에서 처리하는 식으로 진행하였다.
그러다보니 Queue에 위치하는 count의 정보가 3 3 3 2 3 3 과 같이 우선순위를 보장하지 못했다.

중복의 경우에는 dp값을 통해 dp[x] == 0일 때만 접근하도록 하였는데 이 때는 "오답" 이였다.

 

이후 이러한 우선순위 문제를 힙을 통해 해결하고자 하였는데 이 때는 딱히 거리를 기록하는 등 dp의 역할이

없겠다고 생각하였고 이를 지움으로써 "중복 체크"의 문제가 발생했고 "시간 초과" 또는 "메모리 초과"를

받았다.

 

이후 visit배열을 활용하여 중복을 제거하고 로직을 도착한 위치에서 바로 사다리인지 뱀인지를 체크하는 방법

을 통해서 우선순위를 보장되도록 하였다. bfs 순서가 보장이 되도록 로직을 구성하고 visit을 통해 중복을

체크하는 방식.

 

결론) BFS의 경우 순서에 따라 최소거리 등과 같이 우선순위가 보장되도록 로직을 작성하여야함.
(Queue를 쓴다면,PQ일 경우는 중복체크를 잘 해주면 되겠다.) 또한 visit을 쓰는 것을 배열을 사용하는 것 보다

다른 더 편한 방법을 통해 확인하면 되지 않을까?라는 생각에 꺼려하는데, 대부분 문제에서 visit을 쓰는 것이

이해하기 편할 것 같다. 

이 떄 visit배열 구성 시에는 "한번 방문한 자리를 다시 방문했을 때 조건을 만족하는 경우의 수"를 고려하여

구성하는 것이 옳다.