[백준/C++] 16948 번 : 데스나이트 풀이

백준 16948 번 : 데스 나이트

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

16948번: 데스 나이트

---

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

 

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

 

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

---

백준 7562번 - 나이트의 이동과 매우 비슷한 문제이다.

참고 링크 : silver-g-0114.tistory.com/23

[백준/C++] 7562번 : 나이트의 이동 풀이

그러나 나이트의 이동 풀이처럼 queue 에 좌표와 이동 횟수를 저장하면 메모리 초과 에러가 나와서 이동 횟수를 저장하는 배열 cnt 를 만들어 처리했더니 오류가 해결 되었다 ㅎㅎ

 

전체 코드

#include <iostream>
#include <cstring>
#include <queue>
#define MAX 201

using namespace std;

int cnt[MAX][MAX];
int n, start_y, start_x, end_y, end_x;

const int dy[6] = {-2,-2,0,0,2,2};
const int dx[6] = {-1,1,-2,2,-1,1};

int main(void){
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(cnt, -1, sizeof(cnt));
    
    cin >> n;
    cin >> start_y >> start_x >> end_y >> end_x;
    
    queue<pair<int,int>> que;
    que.push(make_pair(start_y, start_x));
    cnt[start_y][start_x] = 0;
    
    while(!que.empty()){
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        
        // 도착한 경우
        if(y==end_y && x==end_x){
            break;
        }
        
        for(int i=0; i<6; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny<0 || nx<0 || ny>=n || nx>=n) continue;
            if(cnt[ny][nx]==-1){
                cnt[ny][nx] = cnt[y][x] + 1;
                que.push(make_pair(ny, nx));
            }
        }
    }
    
    cout << cnt[end_y][end_x] << '\n';
    
    return 0;
}

 

풀이 인증