[백준] 7562-나이트의 이동(C++)

문제링크: https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

bfs 문제입니다. 

처음에 문제를 접했을때 dfs로 풀어야지 하고 신나게 작성하다가 깨닭았네요...

dfs에서는 탐색횟수 문제 때문에 visit여부를 판단해야 하는데 그렇게 되면 대다수의 상황에서 탐색이 이뤄지지 않습니다.

 

1)  큐에 시작좌표를 넣어주고

2)  큐의 시작점과 끝점이 같아질때 까지 반복합니다.

3)  나이트가 갈 수 있는 8가지의 경우에 수를 탐색하며 큐에 넣습니다.

4)  탐색중 도착좌표에 도착하면 arr값을 반환하며 종료합니다.

 

우선 arr는 자신이 몇번째에 도착했는지 카운팅하는 배열입니다. 

이때 if (arr[y + dir_y[i]][x + dir_x[i]]) continue; 이 예외처리가 필요합니다.

그 이유는 기존에 탐색했던 곳이라면 더 빠른경로가 저장되어 있을텐데 그값을 덮는 것은 더 느린 방법으로 해당좌표에 도달하는 값을 저장하는 일이기 때문입니다.

 

 

정답코드입니다. 읽어보고 꼭 직접작성해보세요. :) 화이팅

#include <iostream>
#include <cstring>
using namespace std;

int t = 0, l = 0;
int start_y, start_x, defi_y, defi_x, result;
int que[90000][2] = { 0 };
int started = 0, ended = 0;
int arr[301][301] = { 0 };
int dir_y[8] = { -2,-1, 1, 2, 2, 1,-1,-2 };
int dir_x[8] = {  1, 2, 2, 1,-1,-2,-2,-1 };

int bfs() {
	int cnt = 0;

	que[ended][0] = start_y;
	que[ended][1] = start_x;
	ended++;

	while (started != ended) {
		//cout << ended << endl;
		int y = que[started ][0];
		int x = que[started ][1];
		started++;
		if (y == defi_y && x == defi_x) {
			cout << arr[y][x] << endl;
			return 0;
		}
		
		for (int i = 0; i < 8; i++) {
			if (arr[y + dir_y[i]][x + dir_x[i]]) continue;
			if ((y + dir_y[i]) >= 0 && (y + dir_y[i]) < l && (x + dir_x[i]) >= 0 && (x + dir_x[i]) < l) {
				que[ended][0] = y + dir_y[i];
				que[ended][1] = x + dir_x[i];
				ended++;
				arr[y + dir_y[i]][x + dir_x[i]] = arr[y][x] + 1;
			}
		}
	}

}

int main() {
	cin >> t;

	while (t--) {
		started = 0;
		ended = 0;
		cin >> l;

		cin >> start_y >> start_x;
		cin >> defi_y >> defi_x;

		memset(arr, 0, sizeof(arr));
		
		bfs();
	}

}