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

안유태·2024년 1월 5일
0

알고리즘

목록 보기
221/239

16948번: 데스 나이트

bfs를 이용한 문제이다. 간단한 bfs 구현 문제로 문제에서 주어진 이동 조건을 dy, dx로 구현해 풀어주었다.
쉽게 풀 수 있었던 문제였다. 다만 오타로 인해 시간 낭비가 좀 있었다. 오타를 찾지 못해 시간을 허비하는 경우가 잦은 것 같다. 오타를 줄이도록 노력하자.



#include <iostream>
#include <queue>

using namespace std;

int N, result = -1;
int r1, c1, r2, c2;
int dy[6] = { -2,-2,0,0,2,2 };
int dx[6] = { -1,1,-2,2,-1,1 };
bool check[200][200];

void bfs() {
	queue<pair<pair<int, int>, int>> q;

	q.push({ {r1,c1},0 });
	check[r1][c1] = true;

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int count = q.front().second;

		if (y == r2 && x == c2) {
			result = count;
			break;
		}

		q.pop();

		for (int i = 0; i < 6; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (check[ny][nx]) continue;

			q.push({ {ny,nx},count + 1 });
			check[ny][nx] = true;
		}
	}
}

void solution() {
	bfs();

	cout << result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	cin >> r1 >> c1 >> r2 >> c2;

	solution();
	
	return 0;
}
profile
공부하는 개발자

0개의 댓글