백준 7562_나이트의 이동 문제풀이 in C++

2022년 04월 16일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

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

문제 요구사항

---

• 입력 첫줄에는 Test_case가 주어진다.
• 각 Test_case의 첫줄에는 체스판의 크기가 주어진다.( 4 ≤ l ≤ 300 )
• 각 Test_case의 둘째줄에는 나이트의 현위치, 둘째줄에는 도착지가 있다.
• 이때, 각 Test_case마다 현위치에서 도착지까지 몇 번만에 이동할 수 있는지 출력하라.

접근 방법

---

• 나이트의 이동 방법에 따른 가중치 좌표 nightx와 nighty 배열을 생성해준다.
• 다른 BFS 문제들과 마찬가지로 최소 몇 번만에 갈 수 있는지를 구하는 문제이기 때문에 체스 맵 배열을 선언 해줘서 해당 체스 맵에 계속 이동 횟수를 더해 나간다. (이 문제에서는 체스맵 데이터를 입력받지 않기 때문에 카운트 해나갈 체스맵 2차원 배열 하나면 됨)

풀이 순서

---

1. Test_case의 개수를 입력 받는다.
2. 각 Test_case에 해당하는 데이터(맵크기, 시작점, 도착점)을 입력받는다.
3. BFS 수행
   • q에 시작점 x, y 좌표를 넣어준다.
   • q가 비어있을 때까지 반복문을 돌면서 도착점과 같으면 종료한다.
   • for문을 돌면서 나이트를 이동시키도록 한다.
   • 위 작업 반복 수행
4. 최소 이동거리를 계속 더해나간 배열의 도착점 x, y칸에 최소 이동거리가 담겨져 있으므로, 해당 값을 return 한다.
5. 이 과정을 각 Test_case마다 반복하여 결과를 구한다.

소스코드

---

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct coordinate {
	int x;
	int y;
};

int chessMap[300][300];
bool visitedChessMap[300][300];
int TC, chessMapSize, ans_minMove;
int nightx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int nighty[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
coordinate startC;
coordinate endC;
void moveNightBFS() {
	queue<coordinate> q;
	q.push(startC);
	visitedChessMap[startC.x][startC.y] = true;

	while (!q.empty()) {
		int xx = q.front().x;
		int yy = q.front().y;

		q.pop();
		if (xx == endC.x && yy == endC.y) {
			ans_minMove = chessMap[xx][yy];
			return;
		}
		for (int i = 0; i < 8; i++) {
			int nx = xx + nightx[i];
			int ny = yy + nighty[i];

			if (nx >= 0 && ny >= 0 && nx < chessMapSize && ny < chessMapSize && visitedChessMap[nx][ny] == false) {
				q.push({ nx,ny });
				visitedChessMap[nx][ny] = true;
				chessMap[nx][ny] = chessMap[xx][yy] + 1;
			}
		}
		ans_minMove++;
	}
}

void moveNight() {
	cin >> TC;
	queue<int> result;
	for (int i = 0; i < TC; i++) {
		memset(chessMap, 0, sizeof(chessMap));
		memset(visitedChessMap, false, sizeof(visitedChessMap));
		cin >> chessMapSize;

		cin >> startC.x >> startC.y;
		cin >> endC.x >> endC.y;
		ans_minMove = 0;

		moveNightBFS();
		
		result.push(ans_minMove);
	}
	
	for (int i = 0; i < TC; i++) {
		cout << result.front() << "\n";
		result.pop();
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	moveNight();
	
	return 0;
}

문제 풀이 결과

---