(백준 7562번 나이트의 이동 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 27

날씨가 좋아서 기분이 좋다🌸 꽃이 피어도 알고리즘!!

 

백준 7562번

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

7562번: 나이트의 이동

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

constexpr int MAX_N = 301;
int arr[MAX_N][MAX_N] = { 0 };

void reset_arr(int I){
	for (int i = 0; i < I; i++) {
		for (int j = 0; j < I; j++) {
			arr[i][j] = 0;
		}
	}
}

bool isInside(int x, int y, int I) {
	if (x < 0 || y < 0 || x >= I || y >= I) return false;
	return true;
	
}
int bfs(int startX, int startY, int endX, int endY, int I) {
	if (startX == endX && startY == endY) return 0;
	int dir_x[8] = { -2, -1, 1, 2,2, 1, -1, -2 };
	int dir_y[8] = { -1, -2, 2, 1, -1, -2, 2, 1 };
	queue<pair<int, int>> Q;

	int level = 0;
	Q.push(make_pair(startX, startY));

	while (!Q.empty()) {

		int qsize = Q.size();
		

		for (int j = 0; j < qsize; j++) {
			startX = Q.front().first;
			startY = Q.front().second;
			arr[startX][startY] = 1;
			Q.pop();
			for (int i = 0; i < 8; i++) {
				int nextX = startX + dir_x[i];
				int nextY = startY + dir_y[i];
				if (isInside(nextX, nextY, I) && arr[nextX][nextY] == 0) {
					Q.push(make_pair(nextX, nextY));
					arr[nextX][nextY] = 1;
					if(nextX == endX && nextY == endY) return ++level;
				}
			}
		}
		level++;
	}
	return level;

}

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

	int T; cin >> T;
	vector<int> v(T);
	while (T--) {
		int I; cin >> I;
		reset_arr(I);
		int startX, startY, endX, endY; 
		cin >> startX >> startY;
		cin>> endX>> endY;
		v[T] = bfs(startX, startY, endX, endY, I);

	}
	for (auto i = v.rbegin(); i < v.rend();i++) cout << *i << endl;
}

 

 

주의할 점

vector v(T)로 둘 경우 v는 T개의 원소를 0으로 초기화해서 가지고 있다.여기에 v.push_back을 하면 앞에 초기화된 0이 그대로 있으므로 push_back이 아닌 []을 이용해서 저장해야 한다!