7562_나이트의이동 ( BFS )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다.

 

7562_나이트의이동

 - 이 문제는 체스판의 나이트가 목적지까지 이동하는데 걸리는 최적해를 출력하는 문제이다. 따라서 BFS를 이용하여 움직일 수 있는 모든 경우에 대해 돌려보고 목적지에 가장 빨리 이동한 경우를 출력하면 된다

 - 문제 풀이는 BFS을 이용하여 해결하였다.

 - 자세한 내용은 코드의 주석을 참고하자.

 

	#include <iostream> // io
	#include <queue> // queue
	#include <tuple> // tuple
	#include <cstring> // memset
	using namespace std;
	int T = 0; //테스트 케이스 횟수를 입력받을 변수
	int N = 0; //체스판 한 변의 길이
	//int cur_loc[2] = {0,0}; // 현재 위치
	//int dest_loc[2] = { 0,0 }; //목적지 위치
	int cur_x = 0, cur_y = 0;
	int dest_x = 0, dest_y = 0;
	//방문 확인을 위한 check배열
	bool check[300][300];
	//8방위 방문을 위한 방위행렬 선언 및 초기화
	int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
	int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
	//bfs 탐색을 위한 큐 선언, 이동할 체스판 x,y 좌표와 이동횟수 move를 저장한다.
	queue < tuple<int, int, int>> bfs_q;
	//param x , y : 탐색을 시작할 위피
	int move_knight(int start_x, int start_y)
	{
	//탐색 시작 위치를 큐에 삽입
	bfs_q.push(make_tuple(start_x, start_y, 0));
	//현재 위치를 check배열에 표시
	check[start_y][start_x] = true;
	//탐색할 큐가 없을때까지 루프
	while (!bfs_q.empty())
	{
	//큐에서 탐색할 위치의 기준이 되는 x,y값을 가져온다
	int x = get<0>(bfs_q.front());
	int y = get<1>(bfs_q.front());
	;
	//8방위 탐색을 위한 루프
	for (int i = 0; i < 8; i++)
	{
	int xn = x + dx[i];
	int yn = y + dy[i];
	//탐색할 위치가 체스판을 벗어나면 스킵
	if (xn < 0 || xn >= N || yn < 0 || yn >= N) continue;
	//나이트가 움직인 횟수를 올려준다.
	int cur_move = get<2>(bfs_q.front()) + 1;
	//이동한 위치가 목적지라면 이동한 횟수를 리턴하고 함수 종료
	//if (xn == dest_loc[0] && yn == dest_loc[1])
	if (xn == dest_x && yn == dest_y)
	return cur_move;
	//이동한 위치가 목적지가 아니라면 이동한 위치 정보를 bfs_q에 삽입하여
	//다음 탐색을 이어갈 수 있도록 해주고
	//check 배열에 현재 위치를 방문했음을 표시하여 중복 방문을 방지한다.
	else
	{
	if (!check[yn][xn])
	{
	bfs_q.push(make_tuple(xn, yn, cur_move));
	check[yn][xn] = true;
	}
	}
	}
	//가져온 노드를 반납
	bfs_q.pop();
	}
	}
	int main(void)
	{
	//테스트 케이스 횟수 입력
	cin >> T;
	//결과 출력을 위한 큐 선언
	queue<int> res_q;
	while (T--)
	{
	memset(check, 0, sizeof(check));
	//이전에 사용하고 남은 큐를 모두 비워준다.
	while (!bfs_q.empty()) { bfs_q.pop(); }
	//체스판 한 변의 길이
	cin >> N;
	//현재 나이트의 위치
	//cin >> cur_loc[0] >> cur_loc[1];
	cin >> cur_x >> cur_y;
	//나이트의 목표 위치
	//cin >> dest_loc[0] >> dest_loc[1];
	cin >> dest_x >> dest_y;
	//현재 위치와 목적지가 같을 경우 함수를 호출하지 않고 0을 삽입
	//if (cur_loc[0] == dest_loc[0] && cur_loc[1] == dest_loc[1])
	if (cur_x == dest_x && cur_y == dest_y)
	{
	res_q.push(0);
	}
	else
	{
	//BFS 탐색 함수 호출
	int move_num = move_knight(cur_x, cur_y);
	res_q.push(move_num);
	}
	}
	//res_q에 삽입된 결과값 출력
	while (!res_q.empty())
	{
	cout << res_q.front() << endl;
	res_q.pop();
	}
	return 0;
	}

view raw 7562_나이트의이동.cpp hosted with ❤ by GitHub