[백준 7562: 나이트의 이동] - C++

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;


struct Location //위치정보
{
	Location(int _x, int _y) {
		x = _x;
		y = _y;
	}

	int x;
	int y;
};
int arr[8][2] = { //나이트 방향
	{1,2},
	{2,1},

	{1,-2},
	{2,-1},

	{-1,2},
	{-2,1},

	{-1,-2},
	{-2,-1}
};

int main()
{
	int map[300][300];
	int dis[300][300];

	int total = 0;
	int n;
	cin >> total;

	for (int i = 0; i < total; i++)
	{
		Location Start(0, 0);
		Location Target(0, 0);

		memset(map, 0, sizeof(map));
		memset(dis, 0, sizeof(dis));


		cin >> n;

		cin >> Start.x >> Start.y; //시작위치 입력
		cin >> Target.x >> Target.y; //목표 위치 입력


		if (Start.x == Target.x && Start.y == Target.y) //입력된 값이 동일하면 종료
		{
			cout << 0 << endl;
			continue;
		}


		queue<Location> Q;

		Q.push(Start); //시작지점 넣고 시작

		while (!Q.empty())
		{
			Location tmp = Q.front();
			Q.pop();

			for (int i = 0; i < 8; i++)  //8개 방향 확인
			{
				int nextX = tmp.x + arr[i][0];
				int nextY = tmp.y + arr[i][1];

				if (nextX == Target.x && nextY == Target.y) //목표지점 도착이면 종료
				{
					cout << dis[tmp.x][tmp.y] + 1 << endl; //거리 출력

					while (!Q.empty()) //큐 비워주기
					{
						Q.pop();
					}
					break;

				}

				if (nextX < 0 || nextY < 0 || n <= nextX || n <= nextY)// 범위 이탈하면 무시
				{
					continue;
				}

				if (map[nextX][nextY] == 0)  // 갈수있는곳 확인 시
				{
					map[nextX][nextY] = 1; //갈수 없는곳으로 체크
					Q.push(Location(nextX, nextY)); //다음 큐 삽입
					dis[nextX][nextY] = dis[tmp.x][tmp.y] + 1; //거리 추가 
				}
			}

		}//end of Q while
	}//end of Total

	return 0;
}//end of main