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

나이트의 이동

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

71708

38947

28918

53.086%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

---

문제 해결 방법

- BFS를 이용해 이동 로직을 구현한다.

- 언제 도착하는지를 알기 위해서는 도착 좌표마다 횟수를 누적시켜준다.

#include <iostream>
#include <queue>

using namespace std;

//8방향 이동 배열
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { 1,2,2,1,-1,-2,-2,-1 };

int arr[301][301];
bool visited[301][301];

int textCase = 0;

int l = 0;
int startX, startY = 0;
int endX, endY = 0;

void Clear(int size)
{
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			arr[i][j] = 0;
			visited[i][j] = false;
		}
	}
}

void BFS()
{
	queue<pair<int, int>> q;

	q.push({ startX,startY });

	visited[startX][startY];

	while (false == q.empty())
	{
		pair<int, int> cur = q.front();
		int x = cur.first;
		int y = cur.second;

		//검사를 줄이기 위해 도착했다면 바로 출력
		if (x == endX && y == endY)
		{
			cout << arr[x][y] << endl;
			break;
		}

		q.pop();

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

			if (nx >= 0 && ny >= 0 && nx < l && ny < l && false == visited[nx][ny])
			{
				//이전 좌표의 값을 도착좌표에 더해줌
				arr[nx][ny] = arr[x][y] + 1;
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
}

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

	cin >> textCase;

	for (int i = 0; i < textCase; i++)
	{
		cin >> l;
		cin >> startX >> startY;
		cin >> endX >> endY;

		BFS();

		Clear(l);
	}
}

 

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