백준 7562번 나이트의 이동

문제 링크입니다: https://www.acmicpc.net/problem/7562

BFS(Breadth First Search) 알고리즘으로만 풀 수 있는 문제였습니다.(DFS 불가능)

나이트가 움직일 수 있는 8 방향을 미리 정의한 뒤에 BFS를 통해 현재 위치에서 갈 수 있는 지점을 큐에 집어넣으면서 움직인 횟수를 업데이트하며 풀면 되는 문제였습니다.

cache를 모두 INF로 초기화한 뒤에 min(다음 위치에 저장되어 있는 움직인 횟수, 현재 지점까지 움직인 횟수 + 1)을 통해 최소 이동횟수를 구하면 됩니다.

pair<int, int>를 통해 y와 x의 좌표를 저장하였고 start는 시작지점, destination은 도착지점, 그리고 currentPos는 현재 위치의 좌표입니다!

#include <iostream>

#include <queue>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300;

const int INF = 987654321;

 

typedef struct

{

        int y, x;

}Dir;

 

//나이트가 움직일 수 있는 8가지 방향

Dir moveDir[8] = { {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1} };

 

int I;

pair<int, int> start, destination;

int cache[MAX][MAX];

bool visited[MAX][MAX];

 

void initialize(void)

{

        for (int i = 0; i < MAX; i++)

                 for (int j = 0; j < MAX; j++)

                         cache[i][j] = INF;

}

 

int BFS(int y, int x)

{

        initialize(); //캐쉬 초기화

 

        queue<pair<int, int>> q;

        q.push(make_pair(y, x));

        cache[y][x] = 0;

 

        while (!q.empty())

        {

                 pair<int, int> currentPos = q.front();

                 q.pop();

 

                 if (currentPos.first == destination.first && currentPos.second == destination.second)

                         return cache[currentPos.first][currentPos.second];

 

                 for (int i = 0; i < 8; i++)

                 {

                         int nextY = currentPos.first + moveDir[i].y;

                         int nextX = currentPos.second + moveDir[i].x;

 

                         //이미 방문하지 않았고 체스판 내에서만 움직인다

                         if (0 <= nextY && nextY < I && 0 <= nextX && nextX < I)

                                 if (!visited[nextY][nextX])

                                 {

                                          q.push(make_pair(nextY, nextX));

                                          visited[nextY][nextX] = true; //방문했다고 표시

                                          //최소 이동횟수 update

                                          cache[nextY][nextX] = min(cache[nextY][nextX], cache[currentPos.first][currentPos.second] + 1);

                                 }

                 }

        }

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 memset(visited, false, sizeof(visited));

 

                 cin >> I;

                 cin >> start.first >> start.second;

                 cin >> destination.first >> destination.second;

 

                 cout << BFS(start.first, start.second) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~