[C++] 백준 7562 : 나이트

문제

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

 

 

풀이

시작점에서 목표 지점까지 이동할 수 있는 최소 경로를 구하는 문제이므로, BFS로 풀 수 있었다.

 

코드

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

struct State {
    int y, x, n;
};

int t,l, s_x, s_y, e_x, e_y ;
int visited[301][301];
vector <int> ans;

// 나이트 이동 가능 방법
int dx[8] = {-1, 1, 2, 2, -1, 1, -2, -2 };
int dy[8] = {-2,-2, -1, 1, 2 ,2, -1, 1 };

int main() {
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> l >> s_y >> s_x >> e_y >> e_x;
        
        // 시작점을 큐에 넣고 방문 표시
        queue<State> q;
        q.push({s_y, s_x, 0});
        visited[s_y][s_x] = 1;
        
        // BFS
        while(!q.empty()){
            State cur = q.front();
            q.pop();
			
            // 현재 위치가 목표 위치인 경우,
            // 도달한 경우 
            if(cur.y == e_y && cur.x == e_x){
                ans.push_back(cur.n);
                break;
            }
			
            // 나이트 이동
            for(int i=0; i<8; i++){
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];
				
                // 유효하지 않은 위치(배열 범위를 벗어남)인 경우
                if(ny <0 || ny>=l || nx<0 || nx>=l) continue;
                
                // 이미 방문한 곳인 경우
                if(visited[ny][nx] == 1) continue;

				// 유효한 다음 위치를 큐에 넣고, 방문 표시
                q.push({ny, nx, cur.n+1});
                visited[ny][nx] = 1;
            }
        }

        //  방문 배열 초기화
        for(int i=0; i<l; i++){
            for(int j=0; j<l; j++){
                visited[i][j] = 0;
            }
        }
    }

    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << "\n";
    }
    
    return 0;
}