🤍I [백준 16948/C++] 데스나이트

BOJ 문제 보기

1. 문제

BFS로 풀 수 있는 문제다.

1. 최소 이동 횟수를 구함
2. 이동할 경로가 (r-2,c-1), (r-2,c+1), (r,c-2), (r,c+2), (r+2,c-1), (r+2,c+1) 중 한 칸을 고르는 것임
3. 시작점과 도착점 위치 제공
4. 체스판의 크기 제한

---

2. 해결 과정

BFS을 활용한 미로 탐색 유형과 큰 차이 없이 문제를 해결할 수 있다.

BFS/DFS 문제 해결 유형

• 최소 횟수를 구하는 문제
• 하나의 정점에서 시작해 연결된 모든 정점 방문

최악의 경우 모든 체스판의 칸을 방문해야 하므로 전체 정점의 개수는 $N^{2}$, BFS가 정점을 한 번씩 계산하면 시간 복잡도는 $O(N^{2})$이 된다.

N의 최대 크기가 200이므로 제한 시간 안에 충분히 최적 경로를 탐색할 수 있다.

미로 탐색 문제와 다른점

• x, y 이동 범위
  • 데스나이트에 맞게 상대 위치 dx, dy 배열 확장
• 이동할 수 없는 경우 -1 출력

---

3. 코드

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int n, r1, c1, r2, c2, x, y, nx, ny, i;
int dx[] = { -2, -2, 0, 0, 2, 2 };
int dy[] = { -1, 1, -2, 2, -1, 1 };
int dist[200][200] = { 0, };
queue<pair<int, int>> q;

int main()
{
	scanf("%d %d %d %d %d", &n, &r1, &c1, &r2, &c2);
	q.push(make_pair(r1, c1));

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

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

			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (dist[nx][ny] == 0)
			{
				q.push(make_pair(nx, ny));
				dist[nx][ny] = dist[x][y] + 1;
			}
		}
	}
	if (dist[r2][c2] == 0) printf("-1");
	else printf("%d", dist[r2][c2]);
}

---

4. 생각 정리

코드 작성보다 문제를 제대로 그려보는데 시간을 더 썼다. 문제에 낯선 정보가 보이면 유독 당황해 이해하는데 오래 걸린다. 새로 들어오는 정보를 무작정 차단하려 하지 말고 알고리즘 지식과 잘 엮어보자.

특히 BFS 실버 문제는 기본 알고리즘 코드의 큰 변형 없이 쉽게 문제를 풀 수 있다. 실버 문제로 기본기를 다지고 나서 다양한 확장 문제도 도전해보자.🥰