백준 16948 - 데스 나이트(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16948

16948번: 데스 나이트

BFS를 이용한 간단한 문제입니다.

해당 이동 방향으로 움직일 수 없으면 -1를 이동할 수 있으면 이동한 횟수를 출력하는 문제입니다.

 

체스가 움직일 수 있는 방향은 (-2, -1) / (-2, 1) / (0, -2) / (0, 2) / (2 , -1) / (2, 1) 입니다.

시작 위치를 queue에 넣어준 뒤 BFS 탐색을 시작합니다.

해당 이동방향으로 이동해보면서 MAP의 범위 안에 들어가며 이전에 방문하지 않은 곳을 방문합니다.

 

BFS 탐색이 끝났는 경우에도 도착 위치에 도착하지 못했다면 -1를 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int N;
pair<int, int> start, fin;
int check[201][201];
int dx[6] = { -2,-2,0,0,2,2 };
int dy[6] = { -1,1,-2,2,-1,1 };

int bfs() {
	queue<pair<int, int>> q;
	q.push(start);
	check[start.first][start.second] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (x == fin.first && y == fin.second) break;
		for (int i = 0; i < 6; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 0 && yy >= 0 && xx < N && yy < N) {
				if (check[xx][yy] == 0) {
					check[xx][yy] = check[x][y] + 1;
					q.push({ xx,yy });
				}
			}
		}
	}
	if (check[fin.first][fin.second] == 0) return -1;
	else return check[fin.first][fin.second] - 1;
}

void solve() {
	int ans = bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	cin >> start.first >> start.second >> fin.first >> fin.second;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요