백준 16948 - 데스나이트 - BFS

문제

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

풀이전략

1. 나이트의 이동을 dy, dx배열로 만들어서 BFS로 해결하면 된다.
2. 중복된 위치에 가지 않도록 체크배열을 만들어야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
int dy[] = {-2, -2, 0, 0, 2, 2};
int dx[] = {-1, 1, -2, 2, -1, 1};
bool ch[201][201];

struct deathKnight{
    int r, c, val;
    deathKnight(int aa, int bb, int cc){
        r = aa;
        c = bb;
        val = cc;
    }
};

int BFS(int r, int c, int rF, int cF){
    ch[r][c] = true;
    queue<deathKnight > q;
    q.push(deathKnight(r,c,0));
    while(!q.empty()){
        deathKnight ret = q.front();
        q.pop();

        if(ret.r == rF && ret.c == cF) return ret.val;

        for(int i=0; i<6; i++){
            int rr = ret.r+dy[i];
            int cc = ret.c+dx[i];
            if(rr < 0 || cc <0 || rr>=N || cc >=N) continue;

            if(!ch[rr][cc]){
                ch[rr][cc] = true;
                q.push(deathKnight(rr,cc,ret.val+1));
            }
        }
    }
    return -1;
}
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> N;
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout<<BFS(a,b,c,d)<<endl;
    return 0;
}

소감

이제 이런문제는 잘 풀수있다. 체크배열을 잘 만들어야함을 잊지 말아야한다.