[16928] - 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

접근 방식

처음에 10*10 이라 2차원 배열로 생각하고 풀었다가 1~100까지 그냥 1차원 배열로 받아도 된다는 것을 깨닫고 사다리와 뱀이 있는 곳에는 그 이동할 위치를 저장해 주었다.

 

풀이 방법

- 1에서 시작하니 큐에 1삽입, 방문 표시 해주고 주사위의 눈이 1~6까지 있으니 반복문 돌리기

- 뱀이나 사다리가 있으면 그 위치로 이동, 아닐시 그 자리 그대로

- 이동 후, 또는 현재 값에 굴린 위치에 +1을 해주면 몇번 굴려서 여기까지 왔는지 알 수 있음

- 100번째에 도달하기 위한 굴린 회수가 있으니 출력.

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

namespace Baekjoon.Gold
{
    class _16928
    {
        static void Main_16928(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] board = new int[101];
            bool[] visit = new bool[101];

            //보드에 사다리/뱀 정보 저장
            for(int i = 0; i < n[0] + n[1]; i++)
            {
                int[] m = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                board[m[0]] = m[1];
            }

            //bfs
            Queue<int> que = new Queue<int>();
            visit[1] = true;
            que.Enqueue(1);
            while(que.Count > 0)
            {
                //현재 위치
                int now = que.Dequeue();

                for(int i = 1; i<=6; i++)
                {
                    //주사위를 굴렸을 때 위치가 100넘으면 끊기
                    if (now + i > 100)
                        break;

                    int dice;
                    //만약 뱀이나 사다리 없으면 현재 위치
                    if (board[now + i] == 0)
                        dice = now + i;
                    //뱀이나 사다리 있으면 그걸로 가기
                    else
                        dice = board[now + i];

                    //방문 안했으면
                    if (!visit[dice])
                    {   
                        visit[dice] = true;
                        //현재 몇번짼지 = 굴린위치 +1
                        board[dice] = board[now]+1;
                        //굴릴 위치 넣어주기.
                        que.Enqueue(dice);
                    }
                }
            }

            //Console.WriteLine(string.Join(" ", board));
            Console.WriteLine(board[100]);
        }
    }
}