[C#]백준 16928번: 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

---

• 문제

---

• 문제풀이

100칸짜리 맵을 만든 뒤 BFS방식을 사용하여 탐색을 한 후에 최소 횟수를 출력한다.

 

---

• 코드 1

using System;
using System.Collections.Generic;
using System.Linq;

class SnakeAndLadderGame
{
    static void Main(string[] args)
    {
        List<int> ladderOrSnake = new List<int>(101);
        for (int i = 0; i <= 100; i++)
        {
            ladderOrSnake.Add(-1);
        }


        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        for (int i = 0; i < N + M; i++)
        {
            int[] data = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            if (data[0] < data[1])
            {
                ladderOrSnake[data[0]] = data[1];
            }
            else
            {
                ladderOrSnake[data[0]] = data[1];
            }
        }

        int[] dist = new int[101];
        for (int i = 0; i <= 100; i++)
        {
            dist[i] = -1;
        }
        dist[1] = 0;

        Queue<int> queue = new Queue<int>();
        queue.Enqueue(1);

        while (queue.Count > 0)
        {
            int curPos = queue.Dequeue();

            for (int i = 1; i <= 6; i++)
            {
                int nextPos = curPos + i;
                if (nextPos <= 100 && ladderOrSnake[nextPos] != -1)
                {
                    nextPos = ladderOrSnake[nextPos];
                }

                if (nextPos <= 100 && dist[nextPos] == -1)
                {
                    dist[nextPos] = dist[curPos] + 1;
                    queue.Enqueue(nextPos);
                }
            }
        }

        Console.WriteLine(dist[100]);
    }
}

 

---

• 후기

그래프를 활용한 방식은 까먹지 않게 자주자주 해야겠다.