[백준/CPP/C++] 7562번 - 나이트의 이동

 

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

7562번: 나이트의 이동

 

BFS문제이다. 다른 BFS문제와 다른 점은 상하좌우 한 칸씩 움직이는 것이 아니라 체스의 나이트처럼 움직이는 것이다.

체스의 말은 정면으로 +1, 왼쪽 or 오른쪽으로 +1만큼 움직일 수 있다.

제자리에서 움직일 수 있는 경우의 수는 총 8가지가 있으므로 움직임을 표현할 좌표를 이런식으로 작성해준다.

나이트의 움직임

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

 

그리고 queue에 pair 대신 tuple을 이용하여 풀어보았다.

 

pair는 (x,y)의 쌍으로 이루어지지만, tuple은 (x,y,z)로 이루어진다.

사용 방법은 다음과 같다

queue <tuple <int,int,int>> q_tuple;

q_tuple.push({1,2,3});

 

꺼내는 방법이 약간 생소한데,

 

첫번째 원소 : get<0>(q_tuple);

두번째 원소 : get<1>(q_tuple);

세번째 원소 : get<2>(q_tuple);

 

처럼 이용하면 된다.

 

전체 소스코드

#include <bits/stdc++.h>
using namespace std;

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

int nbfs(int i, int j, int sz, int start, int end) {
	queue <tuple <int, int, int>> q;
	tuple<int, int, int> tmp;
	q.push({ i,j,0 });
	visited[i][j] = 1;
	int cnt = 0;

	while (!q.empty()) {
		tmp = q.front(); q.pop();
		int x = get<0>(tmp), y = get<1>(tmp);

		if (start == x && y == end) {
			cnt = get<2>(tmp);
			break;
		}

		for (int k = 0; k < 8; k++) {
			int nX = x + dx[k];
			int nY = y + dy[k];

			if (nX > -1 && nY > -1 && nX < sz && nY < sz) {
				if (visited[nX][nY] == 0) {
					q.push({ nX, nY, get<2>(tmp) + 1 });
					visited[nX][nY] = 1;
				}
			}
		}
	}

	return cnt;
}

void init2DArr(int arr[][300]) {
	for (int i = 0; i < 300; i++) {
		for (int j = 0; j < 300; j++) {
			arr[i][j] = 0;
		}
	}
}

// A = 17
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int tc; cin >> tc;

	while (tc) {
		int n; cin >> n;
		int start, end; cin >> start >> end;
		int desStart, desEnd; cin >> desStart >> desEnd;

		cout << nbfs(start, end, n, desStart, desEnd) << '\n';
		init2DArr(myMap);
		init2DArr(visited);

		tc--;
	}

}