백준 7562 - 나이트의 이동 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/7562

풀이전략

1. 나이트의 이동을 이전에 dy, dx배열을 만들었던 것처럼 똑같이 만들어준다.
2. 나이트가 이동하지 못하는, 판을 넘어서는 값을 가지 못하도록 조건을 걸어준다.
3. 체크배열을 만들어 나이트가 이미 이동한 부분은 다시 이동하지 않는다.
4. 최단 거리를 구하는 것이므로 BFS로 문제를 해결한다.

코드

#include<bits/stdc++.h>

using namespace std;

int T, N;
// 판에 대한 정보를 넣는 배열
int mp[302][302];
// 나이트의 이동에 관한 배열 
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
// r은 행, c는 열, val은 이동횟수이다. 
struct Knight{
    int r, c, val;
    Knight(int a1, int a2, int a3){
        r= a1;
        c = a2;
        val = a3;

    }
};
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> T;
    for(int t=0; t<T; t++){
        cin >> N;
        memset(mp, 0, sizeof(mp));
        int ta, tb;
        // 시작부분과 이동하려고 할 칸의 관한 정보를 저장한다.
        cin >> ta >> tb;
        Knight start = Knight(ta+1, tb+1, 0);
        cin >> ta >> tb;
        Knight end = Knight(ta+1, tb+1, 0);
		
        // 시작부분을 큐에 넣고 BFS를 시작한다. 
        queue<Knight> q;
        q.push(start);
        mp[start.r][start.c] = -1;
        int flag = 0;
        int res = 0;
        while(!q.empty() && flag == 0){
            Knight knight = q.front();
            // cout << knight.r << " " <<knight.c  << " " << knight.val <<endl;
            q.pop();
            for(int i=0; i<8; i++){
                int rr = knight.r + dy[i];
                int cc = knight.c + dx[i];
                if(mp[rr][cc] == 0 && rr > 0 && cc>0 && rr<=N && cc<=N){
                    if(rr == end.r && cc == end.c){
                        res = knight.val + 1;
                        flag = 1;
                        break;
                    }
                    mp[rr][cc] = -1;
                    q.push(Knight(rr, cc, knight.val+1));
                }
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

소감

이전에 푼 문제인데 왜 그랬는지 모르겠지만 여기서 체크배열을 만들지 않았다. 어떨결에 문제를 해결하긴 했지만, 이 문제에서 체크배열을 만들어 중복되는 위치에 가지 않도록 문제를 해결해야한다. 그것이 더 효율적인 문제해결이다.