[백준 7562] 알고리즘 88일차 : 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

C++ BFS

나이트가 있는 칸, 도달하려는 칸 인덱스가 주어지고 나이트가 도달하려는 칸까지 가는 최단거리를 구하는 문제

나이트가 이동할 수 있는 칸은 위의 사진과 같다.

 

접근방법

나이트가 현 위치에서 갈 수 있는 칸(8개)을 인접한 노드라고 생각하고 그래프 BFS 최단거리 문제로 풀었다.

숨바꼭질 문제랑 유사하다. distances배열과 visit배열을 사용한다.

 

오답노트

제출전에 디버깅에서 런타임에러가 걸렸었다. 원인은 push전 조건문에서

이동할 칸의 방문여부체크를 범위 체크(체스판 안에 있는 칸인지)보다 먼저해서 범위초과 오류가 났다.

 

BFS 최단거리 문제 몇개 풀었다고 호기롭게 한방에 코드쓰고 실행했는데 에러떠서 조금 헤맸지만 깔끔하다 코드는

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dr[8] = {-1,-1,-2,-2,1,1,2,2};
int dc[8] = {-2,2,-1,1,-2,2,-1,1};

int main(){
    int tc;
    cin >> tc;
    for(int t = 0 ; t < tc ; t++){
        int l, qr, qc, dsr, dsc;
        cin >> l >> qr >> qc >> dsr >> dsc;
        
        queue<pair<int,int>> q;
        vector<vector<bool>> visit(l,vector<bool>(l,false));
        vector<vector<int>> distances(l,vector<int>(l,0));
        
        visit[qr][qc] = true;
        q.push(make_pair(qr, qc));
        
        while(!q.empty() && !visit[dsr][dsc]){
            int hereR = q.front().first;
            int hereC = q.front().second;
            q.pop();
            for(int i = 0 ; i < 8 ; i++){
                int thereR = hereR + dr[i];
                int thereC = hereC + dc[i];
                if(thereC >= 0 && thereR >= 0 && thereR < l && thereC < l && !visit[thereR][thereC]){
                    visit[thereR][thereC] = true;
                    distances[thereR][thereC] = distances[hereR][hereC] + 1;
                    q.push(make_pair(thereR, thereC));
                }
            }
        }
        cout << distances[dsr][dsc] << "\n";
    }
    return 0;
}