코딩테스트 준비 - 나이트의 이동

혼자서 다시푸는 코딩테스트 준비 일지 - 25

BFS그래프 이론

Sep 25

5 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 7562.나이트의 이동
사용언어 : C#
난이도 : 중하
풀이시간 : 53m
유형 : BFS, 그래프 이론

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

예제 출력 1 복사

5
28
0

문제 풀이 접근

이 문제의 요구사항은 나이트는 이동할 수 있으며, 시작점이 주어지고, 그 지점에서 도착점을 갈 수 있는지, 간다고한다면, 최소 몇번의 이동을 통해서 갈 수 있는지 출력하는 것이다.

먼저 나이트의 이동 방향을 알아야한다. 첨부된 사진처럼 상하 각각 2칸, 좌우 1칸 움직일 수 있는 것이 나이트의 이동 규칙이다.

이 문제의 방법론은 아래와 같다.
1. 나이트의 이동방법은 총 8가지
2. 상하좌우 한번씩 탐색하던 로직을 나이트의 이동규칙 8가지로 변경해서 탐색하도록 한다.
3. 이동한 횟수를 넣기위해 현재 map[NewPosX,NewPosY] = map[CurPosX,CurPosY] +1 을 한다.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;
using System.IO.Pipes;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }


    public class Solution
    {
        public int mapLength;
        public bool[,] isVisited;
        public int[,] maps;
        public int knightPosX;
        public int knightPosY;

        public int goalPosX;
        public int goalPosY;

        public int[] dx = new int[8] {2,1,-1,-2,-2,-1,1,2};
        public int[] dy = new int[8] {1,2,2,1,-1,-2,-2,-1};

        /*
 * TC 는 3줄 
 * 첫줄 : 체스판 한변의 길이 4 <= a <= 300
 * 크기 : a * a
 * 
 * 체스판은 두 수의 쌍({0,0} ~ {(a-1),(a-1)}) 으로 나타낼 수 있음
 * 
 * 둘째줄 : 나이트의 현재 칸
 * 
 * 셋째줄 : 나이트가 이동하려고 하는 칸
 * 
 */

        public void solve()
        {
            int tc = Int32.Parse(Console.ReadLine());
            mapLength = 0;

            for (int i= 0; i < tc; ++i)
            {
                mapLength = Int32.Parse(Console.ReadLine());
                Init(mapLength);

                string[] curPos = Console.ReadLine().Split(' ');
                knightPosX = Int32.Parse(curPos[0]);
                knightPosY = Int32.Parse(curPos[1]);

                string[] goalPos = Console.ReadLine().Split(' ');
                goalPosX = Int32.Parse(goalPos[0]);
                goalPosY = Int32.Parse(goalPos[1]);

                BFS();
                Console.WriteLine(maps[goalPosX, goalPosY]);
            }
        }

        public void Init(int tc)
        {
            isVisited = new bool[tc, tc];
            maps = new int[tc, tc];

            knightPosX = 0;
            knightPosY = 0;
            goalPosX = 0;
            goalPosY = 0;
        }

        public void BFS()
        {
            Queue<Tuple<int,int>>  q = new Queue<Tuple<int, int>>(); 

            q.Enqueue(new Tuple<int,int>(knightPosX,knightPosY));

            while(q.Count > 0)
            {
                var pos = q.Dequeue();

                if (isVisited[pos.Item1, pos.Item2] == true)
                    continue;

                isVisited[pos.Item1, pos.Item2] = true;

                if (pos.Item1 == goalPosX && pos.Item2 == goalPosY)
                    break;
                // 목적지 도착 시

                for(int i = 0; i < 8; ++i)
                {
                    var newPosX = pos.Item1 + dx[i];
                    var newPosY = pos.Item2 + dy[i];

                    if (isCheckSection(newPosX, newPosY) == false)
                        continue;   

                    if (isVisited[newPosX, newPosY] == true)
                        continue;

                    maps[newPosX,newPosY] = maps[pos.Item1, pos.Item2] + 1;
                    q.Enqueue(new Tuple<int, int>(newPosX, newPosY));
                }
            }
        }

        public bool isCheckSection(int newPosX, int newPosY)
        {
            if (newPosX < 0 || newPosY < 0 || newPosX > mapLength - 1 || newPosY > mapLength - 1)
                return false;

            return true;
        }
    }
}

코드 결과