[BOJ 7562] 나이트의 이동 (C++)

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

나이트의 이동 문제

구현 방법

이 문제의 분류는 BFS입니다.

 

BFS문제는 보통 상, 하, 좌, 우로 움직이는데, 이 문제는 나이트의 이동 방식으로 8가지 방법을 확인해야 합니다.

 

로직 자체는 BFS와 동일하지만, 이동 방향을 8가지로 한다는 차이점 뿐입니다.

 

보통의 BFS는 이동을 위해 다음과 같은 배열을 선언합니다.

int dx[4] = {1, 0, -1, 0}

int dy[4] = {0, 1, 0, -1}

 

하지만 나이트의 이동 문제는 다음과 같이 선언합니다.

int dx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};

int dy[8] = {-1, 1, 2, 2, 1, -1 ,- 2, -2};

 

나이트의 이동이 다음과 같기 때문입니다.

	(x-2,y-1)		(x-2,y+1)
(x-1,y-2)				(x-1,y+2)
		(x,y)
(x,y-2)				(x,y+2)
	(x+2,y-1)		(x+2,y+1)

위 로직을 다음과 같이 구현했습니다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int arr[301][301];
bool vis[301][301];

int dx[8] = {-2,-2,-1,1,2,2,1,-1};
int dy[8] = {-1,1,2,2,1,-1,-2,-2};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int count;
    cin >> count;

    for(int i=0;i<count;i++) {
        //체스판 초기화
        for(int j=0;j<301;j++) {
            for(int k=0;k<301;k++){
                arr[j][k] = 0;
            }
        }
        //vis 초기화
        for(int j=0;j<301;j++) {
            for(int k=0;k<301;k++){
                vis[j][k] = 0;
            }
        }

        //x좌표 y좌표 큐
        queue<pair<int, int>> q;
        int answer = 0;
        
        //체스 판 한변의 길이
        int n;
        cin >> n;
        
        //나이트 위치
        int x,y;
        
        //목표 위치
        int x2,y2;
        
        //나이트 위치 목표 위치 입력 받음
        cin >> x >> y;
        cin >> x2 >> y2;

        //초기값 설정하고 방문 설정
        q.push({x,y});
        arr[x][y] = 0;
        vis[x][y] = 1;

        //BFS시작
        while(!q.empty()) {
            pair<int, int> cur = q.front(); q.pop();

            //현재 위치가 도착 지점이면 출력하고 끝!
            if(cur.first == x2 && cur.second == y2) {
                cout << arr[cur.first][cur.second] << "\n";
                break;
            }
            
            //8가지 방향 탐색
            for(int dir = 0; dir<8;dir++) {
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];
					
                //범위 벗어나면 스킵
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                
                //방문했으면 스킵
                if(vis[nx][ny]) continue;
				
                //새로운 방문 지점에, 이전 방문 지점 + 1 step
                arr[nx][ny] = arr[cur.first][cur.second] + 1;
                
                //방문 표시
                vis[nx][ny] = 1;
                
                //큐에 넣음
                q.push({nx, ny});
            }
        }
    }
}