[백준/C++] 7562번: 나이트의 이동

 

이 문제는 보자마자 이동방향만 기존과 다르게 8방향을 설정하고 bfs를 돌리면 되겠다. 하고 감이 왔다. 하지만 너무 피곤해서 집중력이 안좋아 여러 오타가 발생했고.... 그래서 푸는데 오래 걸렸다.

 

1) index를 주의하자..... 변수이름이 여러개 나오니까 헷갈리지 말고 잘 써야한다. 나같은 경우 cx를 x, cy를 y라고 써놓고 계속 왜틀렸는지 모르고 있었다. 혹은 x와 y를 반대로 쓰지는 않았는지 복붙하다가 x만 두번 쓰지는 않았는지 주의해야함.

2) initialize를 해줘야 다음 test case에서 오류가 안난다.

3) map만 initialize했다가 또 오류가 났다. 이때가 젤 빡쳤는데 queue도 initialize해줘야한다. 전역변수로 설정했던 애를 bfs 블럭안으로 넣어서 bfs 실행될 때마다 다시 변수를 만들도록 바꾸니까 성공했따.

 

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

int map_size;
pair<int, int> Start;
pair<int, int> End;


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

void init() {
	for (int i = 0; i < 301; i++) {
		for (int j = 0; j < 301; j++) {
			map[i][j] = 0;
		}
	}
}

void bfs(int x, int y) {
	queue<pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(x, y), 0));
	map[x][y] = 1;

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

		if (cx == End.first && cy == End.second) {
			cout << cnt << endl;
			return;
		}


		for (int i = 0; i < 8; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || nx >= map_size || ny < 0 || ny >= map_size) continue;
			if (map[nx][ny] == 0) {
				map[nx][ny] = 1;
				q.push(make_pair(make_pair(nx, ny), cnt+1));
			}
		}
	}


}
int main() {

	int test_case;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		
		init();
		cin >> map_size;
		cin >> Start.first >> Start.second;
		cin >> End.first >> End.second;
		bfs(Start.first, Start.second);
	}

	return 0;
}