[99클럽/코딩테스트 챌린지/C++] 나이트의 이동 문제 해결 - BFS를 활용한 최단 거리 탐색

오늘은 체스판 위의 나이트 이동 문제를 해결하면서 BFS(너비 우선 탐색)를 이용해 최단 이동 횟수를 계산하는 방법을 배웠습니다. 나이트가 특정 위치에서 목표 위치까지 최단 거리로 이동해야 하는 문제로, BFS를 사용하여 레벨 단위로 탐색하며 최단 거리를 구할 수 있었습니다.

문제링크 : 

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

 

내 문제 접근 방법

1, 그래프 문제로 인식

• 체스판 위의 칸을 정점으로 보고, 나이트의 이동 가능 경로를 간선으로 연결하여 그래프 형태로 문제를 이해했습니다.

2, BFS로 최단 거리 탐색

• 최단 거리 문제에서는 BFS가 유리하므로, 시작 위치에서 목표 위치로 이동할 때 BFS를 사용했습니다. BFS는 현재 위치에서 가능한 이동들을 순서대로 탐색하며, 가장 먼저 도달하는 경로가 최단 거리임을 보장합니다.

3, 방문 배열을 통한 중복 방지 및 최단 거리 기록

• visited 배열을 통해 이미 방문한 위치를 기록하여 중복 탐색을 방지하고, 방문 시 이동 횟수를 저장하여 각 위치까지의 최단 이동 거리를 기록했습니다.

내 코드

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring> // memset 사용을 위해 필요

using namespace std;

int N,I;
pair<int, int> from;
pair<int, int> to;
int maps[305][305];
int visited[305][305];

vector<pair<int, int>> moves{
    {2,1},
    {1,2},
    {-1,2},
    {-2,1},
    {-2,-1},
    {-1,-2},
    {1,-2},
    {2,-1},
};

int bfs()
{
    queue<pair<int, int>> q;
    q.push(from);
    visited[from.first][from.second] = 1;
    while(!q.empty())
    {
        pair<int, int> current = q.front();
        q.pop();

        if(current.first == to.first && current.second == to.second)
        {
            return visited[current.first][current.second];
        }

        for (auto newPos: moves)
        {
            int newY = newPos.first + current.first;
            int newX = newPos.second + current.second;
            if (newY < 0 || newY > I - 1 || newX < 0 || newX > I - 1) continue;;
            if (visited[newY][newX]) continue;
            visited[newY][newX] = visited[current.first][current.second] + 1;
            q.push({ newY,newX });
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    std::cin >> N;
    while (N > 0)
    {
        std::cin >> I;
        memset(visited,0,sizeof(visited));
        int a, b;
        std::cin >> a >> b;
        from = { a,b };
        std::cin >> a >> b;
        to = { a,b };
        std::cout << bfs() - 1<< std::endl;
        N--;
    }

	return 0;
}

위 코드의 문제 접근 방법

1, 체스판 범위 및 이동 패턴 설정

• 체스판 크기와 나이트의 이동 패턴을 설정하여 BFS 탐색 중 나이트가 이동할 수 있는 모든 방향을 정의했습니다.

2, BFS를 통한 최단 거리 탐색

• BFS를 사용해 시작 위치에서부터 한 레벨씩 목표 위치까지의 거리를 누적하며 탐색했습니다. BFS의 특성상 목표 위치에 가장 먼저 도달할 때가 최단 거리임을 보장합니다.

3, visited 배열을 통한 거리 누적

• visited 배열에 이동 횟수를 누적하여 방문할 때마다 이동 거리를 기록했습니다. 목표 위치에 도달하면 해당 위치의 이동 거리를 반환합니다.

배운 점

나이트의 이동 패턴에 따른 경계 처리 주의 : 나이트의 이동 경로가 다양하므로 각 이동에 대해 체스판의 범위 경계를 확인하여 유효한 이동만 수행해야 한다는 점을 배웠습니다.

결론

이번 문제를 통해 BFS를 사용하여 최단 이동 경로를 탐색하는 방법을 익혔고, 나이트와 같은 다양한 이동 패턴을 가진 문제에서 경계를 확인하고 방문 여부를 체크하는 방법을 배울 수 있었습니다. 앞으로 최단 경로 탐색 문제에서 BFS를 잘 활용할 수 있을 것이라 느꼈습니다.