백준 C# - 7562 +) 풀이

문제에서 최소부분이 있으면 BFS를 이용해야 한다.

앞서 BFS문제들을 풀어봤을때 큰 틀은 비슷한 것을 알 수 있다. 이 문제에서 크게 다른 점이 있다면 나이트의 움직임이다.

직접 좌표를 찍어보자 그러면 이를 각각의 배열들로 표현하면 아래와 같이 나온다.

static int[] dirX = { 2, 1, -1, -2, -2, -1, 1, 2 };
static int[] dirY = { 1, 2, 2, 1, -1 , -2 , -2, -1 };

---

BFS 알고리즘

static void BFS(int x , int y, int n)
{
    Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
    queue.Enqueue(new Tuple<int, int>(x,y));

    while (queue.Count>0)
    {
        Tuple<int, int> now = queue.Dequeue();
        // 만약 도착지에 도착했다면 반복문에서 빠져나온다.
        if(now.Item1 == desX && now.Item2 == desY)
        {
            Console.WriteLine(graph[now.Item1, now.Item2]);
            break;
        }
        for (int i = 0; i < 8 ; i++)
        {
            int newX = now.Item1 + dirX[i];
            int newY = now.Item2 + dirY[i];
         
            if (newX < 0 || newY < 0 || newY >= n || newX >= n) continue;
            if (graph[newX, newY] != 0) continue;

            graph[newX, newY] = graph[now.Item1, now.Item2] + 1;
            queue.Enqueue(new Tuple<int, int>(newX, newY));
    }
}

---

코드 전문

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

namespace baek2
{
    class Program
    {
        static int[] dirX = { 2, 1, -1, -2, -2, -1, 1,2 };
        static int[] dirY = { 1, 2, 2, 1, -1 , -2 , -2, -1 };
        static int desX, desY;
        static int[,] graph;

        static void BFS(int x , int y, int n)
        {
            Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
            queue.Enqueue(new Tuple<int, int>(x,y));

            while (queue.Count>0)
            {
                Tuple<int, int> now = queue.Dequeue();
                
                if(now.Item1 == desX && now.Item2 == desY)
                {
                    Console.WriteLine(graph[now.Item1, now.Item2]);
                    break;
                }
                for (int i = 0; i < 8 ; i++)
                {
                    int newX = now.Item1 + dirX[i];
                    int newY = now.Item2 + dirY[i];

                    if (newX < 0 || newY < 0 || newY >= n || newX >= n) continue;
                    if (graph[newX, newY] != 0) continue;

                    graph[newX, newY] = graph[now.Item1, now.Item2] + 1;
                    queue.Enqueue(new Tuple<int, int>(newX, newY));
                }
            }
        }
        public static void Main()
        {
            int input = int.Parse(Console.ReadLine());
            while (input > 0)
            {
                int n = int.Parse(Console.ReadLine());
                int[] start = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int[] des = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph = new int[311, 311];
                int x = start[0];
                int y = start[1];

                desX = des[0];
                desY = des[1];

                BFS(x, y, n);
                input--;
            }
        }
    }
}