Computer >> 컴퓨터 >  >> 프로그래밍 >> C#

C#으로 체스 나이트가 목적지에 도달하기까지 필요한 최소 이동 횟수 구하기

개요

체스의 나이트(knight)는 L자 형태로 움직이는 말입니다. 체스판 위에서 어떤 칸도 두 번 방문하지 않으면서 모든 칸을 지나가는 문제를 나이트 투어(Knight's Tour)라고 부릅니다. 이 글에서는 C#을 사용해 나이트가 시작 위치에서 목표 위치까지 도달하는 데 필요한 최소 이동 횟수를 BFS(너비 우선 탐색) 알고리즘으로 구하는 방법을 살펴보겠습니다.

나이트 투어의 두 가지 유형

나이트 투어는 경로가 끝나는 방식에 따라 두 가지로 나뉩니다.

  • 닫힌 경로(Closed Tour): 나이트가 시작 칸에서 나이트 이동 거리만큼 떨어진 위치에서 종료되어, 다시 출발점으로 돌아갈 수 있는 경우입니다. 이렇게 되면 전체 경로가 하나의 순환(closed loop)을 이룹니다.
  • 열린 경로(Open Tour): 나이트가 출발점과 무관한 임의의 칸에서 종료되는 경우입니다.

유효한 이동이 되려면 두 가지 조건을 만족해야 합니다. 첫째, 이동 후의 위치가 체스판 내부에 있어야 합니다. 둘째, 그 칸이 아직 방문되지 않은 상태여야 합니다. 일반적으로 아직 방문하지 않은 칸의 값을 -1로 초기화해 두고, 방문 여부를 추적하며 탐색을 진행합니다.

BFS를 활용한 최단 경로 탐색 원리

최소 이동 횟수를 구하는 가장 효율적인 방법은 너비 우선 탐색(BFS)입니다. BFS는 시작점에서 가까운 칸부터 단계별로 넓혀 가며 탐색하기 때문에, 목표 지점에 처음 도달한 시점의 이동 횟수가 곧 최솟값이 됩니다.

알고리즘 동작 과정

  1. 시작 위치를 큐(Queue)에 삽입하고 방문 처리합니다.
  2. 큐에서 칸을 하나 꺼내 목표 위치와 같은지 확인합니다. 같다면 지금까지 누적된 이동 횟수(dis)를 반환합니다.
  3. 나이트가 이동할 수 있는 8가지 방향(dx, dy 배열)을 순회하면서, 새로운 좌표가 체스판 안에 있고 아직 방문하지 않았다면 방문 표시를 하고 큐에 추가합니다.
  4. 큐가 빌 때까지 반복하며, 끝까지 목표에 도달하지 못하면 int.MaxValue를 반환합니다.

C# 구현 예제

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
    public class KnightWalkProblem{
        public class cell{
            public int x, y;
            public int dis;
            public cell(int x, int y, int dis){
                this.x = x;
                this.y = y;
                this.dis = dis;
            }
        }
        static bool isInside(int x, int y, int N){
            if (x >= 1 && x <= N && y >= 1 && y <= N)
                return true;
                return false;
        }
        public int minStepToReachTarget(int[] knightPos, int[] targetPos, int N){
            int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
            int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
            Queue<cell> q = new Queue<cell>();
            q.Enqueue(new cell(knightPos[0], knightPos[1], 0));
            cell t;
            int x, y;
            bool[] visit = new bool[N + 1, N + 1];
            for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                visit[i, j] = false;
            visit[knightPos[0], knightPos[1]] = true;
            while (q.Count != 0){
                t = q.Peek();
                q.Dequeue();
                if (t.x == targetPos[0] && t.y == targetPos[1])
                    return t.dis;
                for (int i = 0; i < 8; i++){
                    x = t.x + dx[i];
                    y = t.y + dy[i];
                    if (isInside(x, y, N) && !visit[x, y]){
                        visit[x, y] = true;
                        q.Enqueue(new cell(x, y, t.dis + 1));
                    }
                }
            }
            return int.MaxValue;
        }
    }
    class Program{
        static void Main(string[] args){
            KnightWalkProblem kn = new KnightWalkProblem();
            int N = 30;
            int[] knightPos = { 1, 1 };
            int[] targetPos = { 30, 30 };
            Console.WriteLine(
                kn.minStepToReachTarget(
                    knightPos,
                    targetPos, N));
        }
    }
}

코드 주요 포인트

  • cell 클래스: 좌표(x, y)와 시작점으로부터의 이동 횟수(dis)를 함께 저장합니다.
  • isInside 메서드: 다음 이동 좌표가 1×1부터 N×N 범위 안에 있는지 검사합니다.
  • visit 배열: 이미 방문한 칸을 표시해 동일한 칸을 중복 탐색하지 않도록 합니다.
  • dx, dy 배열: 나이트가 이동할 수 있는 8가지 L자 방향을 정의합니다.

실행 결과

30×30 크기의 체스판에서 나이트가 (1, 1)에서 (30, 30)으로 이동하는 경우, 실행 결과는 다음과 같습니다.

20

마무리

이처럼 BFS를 활용하면 격자 형태의 판 위에서 최단 이동 횟수를 간결하고 효율적으로 계산할 수 있습니다. 나이트 투어는 그래프 탐색 알고리즘의 대표적인 응용 사례로, 미로 찾기나 최단 경로 문제 등 다양한 분야에 응용할 수 있습니다.