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

문제

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

 

풀이

빨리 길 찾기는 BFS지~

 

q에서 가장 top에 있는 것을 차례대로 꺼낸다.

 

다음 위치가 이동이 가능한지 확인한 후 이동이 불가하면 continue

다음 위치가 이미 visit한 곳인지 확인한 후 그렇다면 continue

 

처음 방문하는 곳이고, 이동이 가능하면 q에 push한다.

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

//moving direction
int dirX[] = { 1,2,2,1,-2,-1,-2,-1 };
int dirY[] = { -2,-1,1,2,-1,-2,1,2 };

void solution()
{
	int I, x, y, targetX, targetY;
	cin >> I >> x >> y >> targetX >> targetY;

	vector<vector<int>>visit(I, vector<int>(I, 0));

	//first
	queue<vector<int>>q;
	q.push({ x,y,0 });

	//start BFS
	while (!q.empty())
	{
		vector<int>now = q.front();
		q.pop();

		//arrive at target
		if (now[0] == targetX && now[1] == targetY) { cout << now[2] << "\n"; return; }

		for (int i = 0; i < 8; i++)
		{
			vector<int>next = { now[0] + dirX[i],now[1] + dirY[i],now[2] + 1 };
			if (next[0] < 0 || next[1] < 0 || next[0] >= I || next[1] >= I)continue;
			if (visit[next[1]][next[0]] != 0) continue;
			visit[next[1]][next[0]]++;
			q.push(next);
		}
	}
}

int main()
{
	int C; cin >> C;
	for (int i = 0; i < C; i++) { solution(); }
}