백준 7562번: 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

아이디어 : BFS

현재 위치에서 나이트가 갈 수 있는 곳을 Queue에 넣고 돌린다.

항상 문제는 BFS 돌리더라도 멈추는 조건을 분명히 해줘야한다.

 

의견 : 아직 BFS로 풀어야하는지, DFS로 풀어야하는지 감이 안 잡힌다.

 

감이 잡히는 사람은 댓글로

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int nTest;
int l;

int nDestY, nDestX;
int nCurY, nCurX;

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

void BFS(int y, int x)
{
	queue<pair<int, pair<int, int>>> q;
	int nChecked[300][300] = { false, };

	q.push(make_pair(0, make_pair(y, x)));
	nChecked[y][x] = true;

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

		q.pop();
		if (cy == nDestY && cx == nDestX)
		{
			cout << cnt << endl;
			break;
		}

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

			if (ny >= 0 && ny < l && nx >= 0 && nx < l)
			{
				if (false == nChecked[ny][nx])
				{
					nChecked[ny][nx] = true;
					q.push(make_pair(cnt + 1, make_pair(ny, nx)));
				}
			}
		}
	}
}

int main(void)
{
	cin >> nTest;

	for (int i = 0; i < nTest; i++)
	{
		cin >> l;
		cin >> nCurX >> nCurY;
		cin >> nDestX >> nDestY;

		BFS(nCurY, nCurX);
	}

	return 0;

}