[BOJ][C#] 16928 뱀과 사다리 게임

LimJaeJun·2024년 1월 2일

algorithm boj

PS/BOJ

목록 보기

84/108

📕 문제

📌 링크

📗 접근 방식

뱀과 사다리 표시:

뱀과 사다리의 시작과 끝 부분을 딕셔너리에 저장한다.

BFS로 이동 횟수 계산:

1부터 100까지의 각 칸에 도착하는 최소 이동 횟수를 계산한다.
시작점인 1부터 출발하여 도착 가능한 모든 칸의 이동 횟수를 계산한다.
현재 좌표에서 주사위의 값인 1 ~ 6까지 이동하여 해당 좌표에서 뱀과 사다리가 있는지 체크
뱀과 사다리가 있다면 이동한 좌표를 기록한다.
현재 좌표가 100이라면 BFS 종료

BFS를 이용해 최단 거리를 찾기 때문에 굳이 이동하기 전의 좌표를 따로 기록해두지 않고 최대한 빠르게 100까지 이동하는 방법만을 탐색하였다.

결과 출력:

100번 칸에 도착하는 최소 이동 횟수를 출력한다.

📘 코드

namespace BOJ
{    
    class No_16928
    {
        static void Main()
        {
            int[] inputs = InputArray();
            int n = inputs[0];
            int m = inputs[1];
            Dictionary<int, int> dict = new Dictionary<int, int>();

            for (int i = 0; i < n + m; i++)
            {
                inputs = InputArray();

                dict.TryAdd(inputs[0], inputs[1]);
            }

            int[] dist = new int[101];

            Queue<int> q = new Queue<int>();
            q.Enqueue(1);
            
            while (q.Count > 0)
            {
                // cur : 현재 좌표
                var cur = q.Dequeue();

                // 현재 좌표가 100이라면 종료
                if (cur == 100)
                {
                    break;
                }

                // 주사위를 굴림 ( 1 ~ 6 )
                for (int dir = 1; dir < 7; dir++)
                {
                    // 이동할 위치의 좌표
                    var next = cur + dir;

                    // 이동할 위치의 좌표에 뱀 혹은 사다리가 있다면 이동한 좌표 업데이트
                    if (dict.TryGetValue(next, out int value))
                    {
                        next = value;
                    }

                    // 99에서 주사위 굴렸을 때 100넘게 체크하기 때문에 next > 100 체크
                    // 이미 방문한 곳 체크
                    if (next > 100 || dist[next] != 0) continue;

                    q.Enqueue(next);
                    dist[next] = dist[cur] + 1;
                }
            }
            
            Console.Write($"{dist[100]}");
        }
        
        static int[] InputArray() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    }
}