[백준(BOJ)] 7562번 : 나이트의 이동 - C++[CPP]

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

나이트의 이동 문제다.

체스에서 나이트를 움직이는 방법은 두 칸 전진 후, 전진한 방향에서 오른쪽 혹은 왼쪽 중 한 방향으로 한 칸을 이동할 수 있다.

움직이는 거리를 dx, dy에 저장하여 나이트의 이동과 동일하게 해 주었다.

그리고 목표지점까지 arr 값을 계속해서 갱신해주었다. 목표지점에 도달하면 arr에 들어있는 값을 출력해주는 로직을 짜 봤다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 301

int T,I;
int current_x,current_y,target_x,target_y;
int arr[MAX][MAX];
int visited[MAX][MAX];
int dx[] = {1,2,2,1,-1,-2,-2,-1};
int dy[] = {2,1,-1,-2,-2,-1,1,2};
queue<pair<int,int>> q;

void reset() {
	while (!q.empty()) q.pop();
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			visited[i][j] = 0;
			arr[i][j] = 0;
		}
	}
}

void bfs(int x,int y) {
    q.push({x,y});
    visited[x][y]=true;
    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        if(a==target_x && b==target_y) {
            cout <<arr[a][b] << "\n";
            while(!q.empty()) {
                q.pop();
            }
            break;
        }
        for(int i=0;i<8;i++) {
            int na = a + dx[i];
            int nb = b + dy[i];
            if(0<=na && 0<=nb && na <I && nb < I && !visited[na][nb]) {
                q.push({na,nb});
                visited[na][nb]=true;
                arr[na][nb]=arr[a][b]+1;
            }
        }
    }
}

int main() {
    cin >> T;
    for(int i=0;i<T;i++) {
        cin >> I;
        cin >> current_x >> current_y;
        cin >> target_x >> target_y;

        bfs(current_x,current_y);
        reset();
    }
}

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!