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

문제 링크

7562번: 나이트의 이동

풀이

BFS로 푸는 문제. 다른 문제와 다른건 상하좌우가 아니라는 점뿐이다.

1. BFS 함수에 현재 나이트의 위치와 목표 위치를 넘겨준다.
2. q에 현재 위치를 push하고 빌 때까지 반복한다.
   2-1. 새로 이동하는 위치가 범위 밖이거나 방문했으면 continue
   2-2. 아니면 이 전에 왔던 위치에서 +1해주고 방문처리, q에 push해준다.
   2-3. 나이트가 목표 지점에 도착하면 return 해준 뒤 dist[goalY][goalX]를 출력한다.

코드

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

int n;
vector<vector<int>> visit;
vector<vector<int>> dist;

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

void BFS(int y, int x, int goalY, int goalX)
{
	dist[y][x] = 0;
	visit[y][x] = 1;
	
	queue<pair<int, int>> q;
	q.push({ y,x });

	while (!q.empty())
	{
		int ty = q.front().first;
		int tx = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++)
		{
			int ny = ty + dy[i];
			int nx = tx + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
			if (visit[ny][nx]) continue;

			dist[ny][nx] = dist[ty][tx] + 1;
			visit[ny][nx] = 1;
			q.push({ ny,nx });

			if (ny == goalY && nx == goalX) return;
		}
	}
}

int main(void)
{
	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n;
		visit.resize(n, vector<int>(n));
		dist.resize(n, vector<int>(n));

		int curY, curX;
		int goalY, goalX;
		cin >> curY >> curX;
		cin >> goalY >> goalX;

		BFS(curY, curX, goalY, goalX);

		cout << dist[goalY][goalX]<<endl;

		visit.clear();
		dist.clear();

	}
}