[C#] 뱀과 사다리 게임

백준 문제

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

풀이 후기

1. 분석

자승자박이라는 말이 있다. 그니까 알면서 당했다. 문제를 보면서 처음 생각이 든 것은 무작정 긴 사다리를 타는 것이 좋을까? 였다. 생각은 잘 안 나는데 뒤로 가는 것이 좋은 케이스가 있으리라 생각이 났다. 어이없지만 그렇기에 DP로 풀어야지 라는 결론이 났다.

이 문제는 DP로 못 푼다. 나름 DP로도 풀 수는 있을 것 같은데, [뒤의 칸 숫자를 갱신하면, 다시 뒤에서부터 훑기] 라는 조건이 뭔가 좀... (정정, 내 수준으로는 불가능) 그냥 평범하게 BFS로 풀었다.

2. 실행 결과

3. 결과

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

class Baekjoon
{
    public void Solution((int, int)[] arr)
    {
        var warp = new int[101];
        for (var i = 0; i < arr.Length; i++)
        {
            warp[arr[i].Item1] = arr[i].Item2;
        }

        var visited = new bool[101];
        visited[1] = true;
        
        var q = new Queue<(int, int)>();
        q.Enqueue((1, 0));
        
        while (true)
        {
            var node = q.Dequeue();
            
            for (var dice = 1; dice < 7; dice++)
            {
                var pos = node.Item1 + dice;
                if (visited[pos])
                {
                    continue;
                }
                
                if (100 <= pos)
                {
                    Console.WriteLine(node.Item2 + 1);
                    return;
                }
                
                if (warp[pos] != 0)
                {
                    pos = warp[pos];
                }
                
                q.Enqueue((pos, node.Item2 + 1));
                visited[pos] = true;
            }
        }
    }

    static void Main(string[] args)
    {
        var nums = Console.ReadLine()!.Split(" ");

        var arr = Enumerable.Range(0, int.Parse(nums[0]) + int.Parse(nums[1])).Select(_ =>
        {
            var read = Console.ReadLine()!.Split(" ");
            return (int.Parse(read[0]), int.Parse(read[1]));
        }).ToArray();

        new Baekjoon().Solution(arr);
    }
}