[BOJ알고리즘, C++]#7562_나이트의 이동, 미로 찾기 유형, 너비 우선 탐색,

#1. 문제

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

 

---

 

#2. 풀이

 

1. 너비 우선 탐색, BFS

[자료구조]#6_그래프

너비 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나로, 큐 자료구조를 활용하여 현재 정점의 인접 정점들을 우선적으로 탐색하는 방법입니다.

 

2. 미로 찾기 유형, 알지?

1. 미로 찾기 유형 문제입니다. 현재 정점에서 어떤 방향의 인접 정점들을 방문할 수 있는지 설정하고, 인접 정점들에 대한 탐색을 진행해 줍니다.
2. 마지막으로, 도착 정점에 방문했을 경우 카운트한 정점 개수를 최소 값으로 업데이트해줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/7562
*   @문제: 체스에서 나이트가 지정된 칸까지 이동하기 위해 필요한 움직임 횟수
*   @설명
        1. 미로 찾기 문제
        2. 무 방향 그래프 -> 방문 여부 체크!
*/


#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;

#define MAX 300
typedef pair<int,int> p;

int T, I;
p start, dest;
vector<int> board[MAX];
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs()
{
    // 위치 좌표 & 움직인 횟수
    queue<pair<pair<int,int>, int>> q;
    // 방문 여부
    vector<vector<bool>> visited(I, vector<bool>(I, false));
    // 결과 값
    int res = INT_MAX;

    q.push({start, 0});
    visited[start.first][start.second] = true;

    while(!q.empty())
    {
        p cPos = q.front().first;
        int cnt = q.front().second;

        q.pop();

        int cy = cPos.first;
        int cx = cPos.second;

        if(cPos == dest)
        {
            res = min(res, cnt);
        }

        for(int i=0; i<8; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if(ny < 0 || ny >= I || nx < 0 || nx >= I || visited[ny][nx]) continue;

            visited[ny][nx] = true;
            q.push({{ny,nx}, cnt+1});
        }
    }

    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while(T--)
    {
        cin >> I;
        cin >> start.first >> start.second;
        cin >> dest.first >> dest.second;

        bfs();
    }

    return 0;
}

 

---