7562번: 나이트의 이동

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

7562번: 나이트의 이동

1. 문제 분석

맨 처음엔 이동하는 규칙을 찾아서 계산해서 풀어보려고 했는데,

그러기엔 체스판의 범위라는 변수가 있어서 BFS로 풀어야 하나라는 생각을 했다.

체스판의 크기가 300*300이니까 시간 안에 가능하다고 생각했다.

 

2. 코드 작성

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

queue<pair<int,int>> q;
int check[300][300];

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

pair<int, int> now, target, move_k;

void bfs() 
{
	while (q.empty() == 0)
	{
		cnt++;
		int queue_size = q.size();
		for (int i = 0;i < queue_size;i++)
		{
			int y = q.front().first, x = q.front().second;
			q.pop();
			for (int i = 0;i < 8;i++)
			{
				int move_y = y + dy[i], move_x = x + dx[i];
				move_k = { move_y, move_x };
				if (check[move_y][move_x] == 0 && move_y >= 0 && move_y < size_c && move_x < size_c && move_x >= 0)
				{
					if (target == move_k)
					{
						cout << cnt<<"\n";
						return;
					}
					check[move_y][move_x] = 1;
					q.push(move_k);
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int T;
	
	cin >> T;
	while (T--)
	{
		cin >> size_c >> now.first >> now.second >> target.first >> target.second;
		if (now == target) cout << 0<<"\n";
		else
		{
			q.push(now);
			check[now.first][now.second] = 1;
			bfs();
			for (int i = 0;i < size_c;i++)
			{
				for (int j = 0;j < size_c;j++)
				{
					check[i][j] = 0;
				}
			}
			cnt = 0;
			while (q.empty() == 0)
			{
				q.pop();
			}
		}
	}
	return 0;
}

3. 키워드

#BFS