18404번 현명한 나이트 | BFS | 백준 18404 C++ 코드

 

 

이번 포스팅은 백준 18404번 현명한 나이트입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/18404

18404번: 현명한 나이트

 

 

 

기본 알고리즘

최단 경로 = BFS (너비 우선 탐색)

 

 

 

전체 코드

 

//백준18404 현명한 나이트                                                        
 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
 
int N; //체스판 크기
int A, B; //상대 말 위치
const int MAX = 502;
int path[MAX][MAX];
bool visited[MAX][MAX];
int dy[] = {-1,1,-2,2,-2,2,-1,1};
int dx[] = {-2,-2,-1,-1,1,1,2,2};
queue<pair<int, int>> q;
int ans[1001]; //최소 이동 수 저장 배열
 
void BFS(int y, int x) {
    path[y][x] = 0;
    visited[y][x] = true;
    q.push(make_pair(y, x));
 
    while (!q.empty()) {
        y = q.front().first;
        x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny<=0 || nx<=0 || ny>N || nx>N)
                continue;
            if (visited[ny][nx] == 0) {
                visited[ny][nx] = true;
                path[ny][nx] = path[y][x] + 1;
                q.push(make_pair(ny, nx));
            }
        }
    }
}
 
void reset() { 
    int visited = { 0, };
    int path = { 0, };
}
 
int main() {
    int M, X, Y;
    scanf("%d %d", &N, &M);
    scanf("%d %d", &X, &Y);
    
    for(int i=0;i<M;i++) {
        scanf("%d %d", &A, &B);
        BFS(X, Y);
        ans[i] = path[A][B]; //최소 이동 수 배열에 저장
        reset(); //초기화
    }
 
    for (int i = 0; i < M; i++) {
        printf("%d ", ans[i]);
    }
 
}