[C++] 백준 7562번 : 나이트의 이동

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

진짜 쓰는거 완전 까먹었었당..;;;

확실히 10일전과 비교했을 때, 실력이 많이 는 것 같다.

스터디 팀원이 알려준 문제풀이 꿀팁으로 문제를 더욱 차분히 풀 수 있게 된 것같다.

진짜 너무 고맙다..ㅜ

처음에 왕창 틀렸었다.

 

ㅜㅜ

 

 

1. 문제 해석

1. test case만큼 반복
2. n * n 보드의 n값 입력
3. 나이트 출발 위치
4. 나이트 도착 위치

즉, 나이트의 출발 -> 도착 까지 이동할 때의 최소 횟수를 구하는 문제

 

이런 최단 경로를 구하는 문제는 bfs 즉, 깊이 우선 탐색을 통해 구현하면 된다.

 

 

2. 문제 풀이

주석문으로 대충 알고리즘 흐름을 써 두고
해당 알고리즘을 하나씩 짜는 방식으로 구현했다.

 

 

이 방법이 진짜 제일 좋은 듯하다.

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int test_case;
    cin >> test_case;

    while (test_case--)
    {
        /* code */
        int l;
        cin >> l;
        vector<vector<bool>> isVisited(l, vector<bool>(l, false));
        int start_x, end_x, start_y, end_y;
        cin >> start_x >> start_y >> end_x >> end_y;

        queue<tuple<int, int, long long>> qt; // x,y,turn
        long long minTurn = LONG_LONG_MAX;

        // 시작과 끝점이 같은 경우
        if (start_x == end_x && start_y == end_y)
        {
            cout << 0 << "\n";
            continue;
        }

        // 2. (i,j)에 방문하지 않았다면 큐에 추가 + 방문횟수는 0으로 시작
        qt.push({start_x, start_y, 0});
        isVisited[start_x][start_y] = true;

        // 3. 큐에서 좌표 pop --> 큐가 빌때까지 while문 반복
        while (!qt.empty())
        {
            /* code */
            auto [x, y, turn] = qt.front();
            qt.pop();

            // 5. 갈수있는 범위 내에 존재하는 좌표인지 확인 (8방향 비교)
            for (int k = 0; k < 8; k++)
            {
                int nx = x + dx[k];
                int ny = y + dy[k];

                // 5.1. 만약 갈 수 없는 좌표거나, 이미 방문했었다면 -> continue;
                if (nx < 0 || nx >= l || ny < 0 || ny >= l || isVisited[nx][ny])
                {
                    continue;
                }

                // 5.2. 만약 해당 좌표가 도달 위치라면, 최소 방문 횟수인지 비교하고 업데이트
                if (nx == end_x && ny == end_y)
                {
                    // cout << turn + 1 << endl;
                    minTurn = min(minTurn, turn + 1);
                }

                // 5.3. 큐에 좌표+ (이동횟수 + 1) 추가
                qt.push({nx, ny, turn + 1});
                isVisited[nx][ny] = true;
            }
        }

        cout << minTurn << "\n";
    }
}