[백준] 7562번 나이트의 이동 C++ 문제풀이

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

7562번: 나이트의 이동

문제 풀이

맨 처음에 DFS를 이용해 풀었는데 Stack Overflow가 나왔다.

아무래도 깊이 우선 탐색은 무한정으로 깊어지는 경우에는 사용하기가 어려운 것 같다.

따라서 Queue와 BFS를 이용해서 문제를 해결했다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

int N, x, y, futu_x, futu_y;
int dx[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dy[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };

bool visited[301][301] = { false };

int bfs(int row, int col, int cnt) {
	queue<pair<pair<int, int>,int>> que;
	que.push(make_pair(make_pair(row, col), cnt));
	visited[row][col] = true;
	while (!que.empty()) {
		pair<pair<int, int>, int> point = que.front();
		que.pop();
		int x = point.first.first;
		int y = point.first.second;
		int cnt = point.second;
		if (x == futu_x && y == futu_y) {
			return cnt;
		}
		for (int i = 0; i < 8; i++) {
			int x_num = x + dx[i];
			int y_num = y + dy[i];
			if (x_num >= 0 && x_num < N && y_num >= 0 && y_num < N) {
				if (visited[x_num][y_num] == false) {
					visited[x_num][y_num] = true;
					que.push(make_pair(make_pair(x_num, y_num), cnt + 1));
				}
			}
		}
	}
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		cin >> x >> y >> futu_x >> futu_y;
		visited[x][y] = 1;
		int max_num = bfs(x, y, 0);
		cout << max_num << '\n';

		// 초기화!
		max_num = 0;
		for (int j = 0; j < N; j++) {
			for (int t = 0; t < N; t++) {
				visited[j][t] = 0;
			}
		}
	}
}