백준 7562:나이트의 이동

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

이번문제는 나이트의 이동입니다. BFS활용 문제인데요. 체스판이 주어지면 나이트가 이동하는데, 목적지까지 몇번만에 갈 수 있는지 계산하는 문제입니다. 좌표가 8방향이고, 한 칸씩 이동하는 것이 아닐뿐이고 다른 BFS와 같은 것 같아요. visited 배열을 bool 자료형이 아닌, int 형으로 해서 방문체크를 함과 동시에 몇번만에 이동했는지 체크할 수 있게 했어요.

밑에는 제 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef struct rc {
    int r;
    int c;
}pos;  //좌표
 
int r[8] = { -1,-2,-2,-1,1,2,2,1 }; //8방 탐색
int c[8] = { -2,-1,1,2,2,1,-1,-2 }; //8방 탐색
vector<vector<pos> > chess;
vector<vector<int> > visited;
int I;
 
bool isSafe(int r, int c) {  //범위체크
    if ((r<0 || r>=I) || (c<0 || c>=I)) return false;
    else return true;
}
 
int cntMove(pos from, pos to) {
    queue<pos> q; q.push(from); int nowR = q.front().r, nowC = q.front().c;
    visited[q.front().r][q.front().c] = 1;  //시작점을 큐에넣고 방문했다고 체크
    while (!q.empty()) {
        pos now = q.front();
        for (int i = 0; i < 8; i++) {  //8방 탐색
            pos next; next.r = now.r - r[i]; next.c = now.c - c[i];
            if (isSafe(next.r, next.c) && !visited[next.r][next.c]) {  //방문 가능, 방문하지 않았다면
                visited[next.r][next.c] = visited[now.r][now.c] + 1;  //방문체크+1
                q.push(next);  //큐에 넣기
            }
        }
        q.pop();
    }
 
    return visited[to.r][to.c] - 1;  //목적지에 몇번만에 갔는지 return
}
 
int main(void) {
    int testCase;
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        cin >> I;                            //I사이즈 만큼 I*I체스판을 만들어요
        chess.resize(I); visited.resize(I);
        for (int i = 0; i < I; i++) {
            chess[i].resize(I);
            visited[i].resize(I);
        }
        pos from, to;
        cin >> from.r >> from.c;  //시작 좌표
        cin >> to.r >> to.c;      //타겟 좌표
 
        int cnt = cntMove(from, to);
        cout << cnt << endl;
 
        chess.clear(); visited.clear();
    }
 
    return 0;
}