[백준] 나이트의 이동 BFS

나이트의 이동 7562

    //
    // Created by JayPark on 2020/05/10.
    //

    #include "algo.h"
    using namespace std;
    // 값 3개가 필요하다.
    /* 1. 체스판의 크기
     * 2. 현재 나이트의 위치
     * 3. 이동해야하는 칸
     * */
    int T, N;
    int map[301][301];
    bool chk[301][301];
    // 시작 위치, 종료위치
    typedef struct Start_Point {
        int x, y;
    } sp;
    // 도착해야하는 위치
    int ex, ey;
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    int main(){
        cin >> T;
        while(T--){
            // 체스판의 크기
            cin >> N;
            sp s;
            cin >> s.x >> s.y;
            cin >> ex >> ey;
            // 큐 생성
            queue<sp> q;
            // 큐에 구조체 삽입
            q.push(s);
            // 현재위치 체크
            chk[s.x][s.y] = true;
            // bfs
            while(!q.empty()){
                // 새로운 객체변수에 큐의 front값을 담는다.
                sp now = q.front();
                // 도착을 했다면
                if(now.x == ex && now.y == ey){
                    cout << map[ex][ey] << endl;
                    break;
                }
                // 그리고 큐를 비워준다.
                q.pop();
                for(int k=0;k<8;k++){
                    // 다음 이동할 위치를 테스트하기위한 변수
                    sp next;
                    // 다음으로 이동할 좌표값
                    next.x = now.x + dx[k];
                    next.y = now.y + dy[k];
                    // 체스판 범위를 초과하는지 확인
                    if(next.x < 0 || next.y < 0 || next.x >= N || next.y >= N) continue;
                    // 갔던곳인지 확인
                    if(chk[next.x][next.y]) continue;

                    // 큐에 저장.
                    q.push(next);
                    map[next.x][next.y] = map[now.x][now.y] + 1;
                    // 한번 갔다는 것을 체크.
                    chk[next.x][next.y] = true;
                }
            }
            // map 초기화
            memset(map, 0, sizeof(map));
            // 체크배열 초기화
            memset(chk, false, sizeof(chk));
        }
    }