[C++]백준 - 7562번 문제

7562번: 나이트의 이동 (acmicpc.net)

7562번: 나이트의 이동

 

7562번 : 나이트의 이동

---

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력

---

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

 

출력

---

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

 

 

---

 

생각해 볼 점

---

최소 경로 탐색이므로 BFS를 이용할 것입니다.

 

BFS를 사용하면, 가능한 모든 경로를 Step 한번마다 확인하여, 목적지에 도착했는지 가장 먼저 체크할 수 있습니다.

 

DFS는 결국 가능한 모든 경로를 확인해서 목적지에 도착한 경우들의 최소값을 비교해야하므로, 수행시간이 엄청나게 길어집니다.

 

나이트는 한번의 이동에 8가지 경우의 수가 있는데, 체스판을 넘어가지 않는 범위 내에서 BFS 알고리즘으로 탐색합니다.

 

 

코드

---

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

int main() 
{
    int T;
    cin >> T;
    
    int move_x[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
    int move_y[8] = {-1, -2, 2, 1, 1, 2, -2, -1};
    
    for(int i = 0; i < T; i++)
    {
        int I;  //체스판 크기
        cin >> I;
        
        int count = 0;
        bool **visited = new bool*[I];
        for(int i = 0; i < I; i++)
        {
            visited[i] = new bool[I];
            fill_n(visited[i], I, false);
        }
        
        pair<int, int> knight;
        pair<int, int> des;
        
        cin >> knight.first >> knight.second;
        cin >> des.first >> des.second;
        
        queue<pair<int, int>> q;
        q.push(knight);
        visited[knight.second][knight.first] = true;
        
        
        //BFS 알고리즘
        while(!q.empty())
        {
            //목적지 도달
            if(visited[des.second][des.first]) break;
            
            count++;
            vector<pair<int, int>> next_bfs;
            
            while(!q.empty())
            {
                pair<int, int> current = q.front();
                q.pop();
                
                for(int i = 0; i < 8; i++)
                {
                    //나이트의 움직임
                    int new_x = current.first + move_x[i];
                    int new_y = current.second + move_y[i];
                    
                    //예외처리
                    if(new_x < 0 || I <= new_x || new_y < 0 || I <= new_y) continue;
                    if(!visited[new_y][new_x])
                    {
                        next_bfs.push_back({new_x, new_y});
                        visited[new_y][new_x] = true;
                    }
                }
            }
            for(pair<int, int> p : next_bfs) q.push(p);
        }
        
        //동적할당 해제
        for(int i = 0; i < I; i++) delete[] visited[i];
        delete[] visited;
        cout << count << "\n";
    }
	return 0;
}

 

그 외

---