백준 7562번 - 나이트의 이동, BFS를 이용한 그래프 순회 문제 (with C++)

문제 소개

이번에 풀이한 문제는 7562번 나이트의 이동 문제입니다. solved.ac 기준으로 실버 1 난이도이긴 하나, BFS 알고리즘을 적용해야 하는 구조를 이해하면, 쉽게 풀 수 있는 문제였습니다!! 

 

 

 

문제 링크입니다!! 😀

7562번: 나이트의 이동

---

문제 설명 및 아이디어

나이트의 움직임 종류

임의의 사이즈의 체스판 위에서 나이트가 놓여 있을 때, 입력받은 도착 지점으로 이동하는데 최소 몇 번 움직여야 하는지 구하는 것이 목표인 문제입니다.

 

따라서 나이트의 현재 위치에 따라서 다음 번에 이동할 수 있는 위치가 계속해서 새로 발생합니다. (아마 8가지 일 것입니다. 이동하기 전 위치를 고려하면 7가지이긴 합니다!)

 

이 아이디어에 따라 이번 문제를 풀기 위해 저는 BFS (Breadth-First Search, 너비 우선 탐색) 방식의 그래프 순회 알고리즘을 적용해서 풀이했고, 소스 코드는 다음과 같습니다!!

---

제출 소스 코드 (C++)

#include <iostream>
#include <queue>
#define MAX 301 

using namespace std;

int t, n;
int cur_x, cur_y;
int des_x, des_y;
// 방문 처리를 위한 배열 (중복 방문을 피하기 위해)
bool visited[MAX][MAX] = { false, };
// 입력 값을 한 번에 받도록 작성한 함수
void input() {
	cin >> n;
	cin >> cur_x >> cur_y;
	cin >> des_x >> des_y;

	return; 
}
// visited 배열을 초기화 하기 위한 함수
void initialize() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			visited[i][j] = false;
		}
	}
	return;
}

bool inRange(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n;
}

int BFS() {
	queue<pair<pair<int, int>, int>> q;

	q.push({ { cur_x, cur_y }, 0 });
	visited[cur_x][cur_y] = true;

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


	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int next_cnt = cnt + 1;

			if (!inRange(nx, ny) || visited[nx][ny])
				continue;

			if (nx == des_x && ny == des_y) {
				return next_cnt;
			}
			else {
				visited[nx][ny] = true;
				q.push({ {nx, ny}, next_cnt });
			}
		}
	}

	return 0;
}

int main() {
	int t;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;

	while (t--) {
		input();
		initialize();

		cout << BFS() << "\n";
	}

	return 0;
}

BFS의 반환 값은 최소 이동 거리로 도착 지점에 도달하는 즉시, BFS 함수가 종료되도록 구현했습니다!

 

도움이 되셨다면, 로그인이 필요 없는 좋아요 ❤ 한 번 부탁드립니다!! 👍🏼👍🏼