백준 16948 c++ "데스 나이트" -PlusUltraCode-

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

[필자 사고]

간단한 BFS 문제다.

문제에서 주어진 방향대로 잘 정리하고 BFS node 에count 를 심어나서 특정 위치까지 도달하면

BFS 종료시키면 된다 .

 

아래는 자세한 코드 해설이다.

[코드 해설]

isInside(int sero, int garo)

• 좌표 (sero, garo)가 보드 범위 안에 있는지 확인한다.
• 0 ≤ sero, garo < N이면 true, 아니면 false를 반환한다.
• 이동 가능한 후보 좌표를 필터링할 때 사용한다.

---

BFS()

• 최단 이동 횟수를 구하는 핵심 함수로, 너비 우선 탐색을 수행한다.
• 큐에 시작점 (sero1, garo1)과 이동 횟수 0을 넣고 시작한다.
• 큐에서 하나씩 꺼내며:
  • 현재 좌표가 도착점 (sero2, garo2)이면 현재까지의 이동 횟수를 resultCount에 기록하고 종료한다.
  • 6가지 이동 벡터(dy, dx)를 이용해 다음 좌표들을 생성한다.
  • 각 다음 좌표에 대해 보드 범위를 벗어나지 않고(isInside), 아직 방문하지 않았다면:
    • 방문 체크(visited[nextSero][nextGaro] = true) 후, 이동 횟수 +1을 붙여 큐에 넣는다.
• 큐가 빌 때까지 도착점에 도달하지 못하면 resultCount는 초기값 -1로 남는다(도달 불가 의미).

---

main()

• 보드 크기 N, 시작 좌표 (sero1, garo1), 도착 좌표 (sero2, garo2)를 입력받는다.
• 방문 배열 visited를 N×N 크기의 false로 초기화한다.
• BFS()를 호출해 최단 이동 횟수를 계산한다.
• 계산 결과 resultCount를 출력한다. 도달 가능하면 최소 이동 횟수, 불가능하면 -1이 출력된다.

---

보조 구성 요소

• struct Node { int sero; int garo; int count; };
  • BFS 큐에 넣을 요소의 형태를 정의한다. 좌표와 거기까지의 이동 횟수를 함께 보관한다.
• 이동 벡터 dy[6], dx[6]
  • 말의 가능한 6가지 이동을 나타낸다.
  • 현재 좌표 (y, x)에서 다음 좌표는 (y + dy[i], x + dx[i])로 계산한다.
• visited
  • 각 좌표를 한 번만 방문하도록 하는 체크 배열로, BFS에서 중복 방문을 막아 시간 복잡도를 줄이고 최단 경로 성질을 보장한다.

[소스 코드]

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

typedef struct Node {
	int sero;
	int garo;
	int count;
};

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

int N;
int sero1, garo1, sero2, garo2;
vector<vector<bool>> visited;

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

int resultCount = -1;

void BFS() {
	queue<Node> myQueue;
	myQueue.push({ sero1,garo1,0 });
	visited[sero1][garo1] = true;

	while (!myQueue.empty()) {
		int nowSero = myQueue.front().sero;
		int nowGaro = myQueue.front().garo;
		int nowCount = myQueue.front().count;
		myQueue.pop();

		if (nowSero == sero2 && nowGaro == garo2) {
			resultCount = nowCount;
			return;
		}

		for (int i = 0; i < 6; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];

			if (isInside(nextSero, nextGaro) == false)continue;
			if (visited[nextSero][nextGaro])continue;
			visited[nextSero][nextGaro] = true;
			myQueue.push({ nextSero,nextGaro,nowCount + 1 });
		}
	}
}

int main(void) {
	cin >> N;
	cin >> sero1 >> garo1 >> sero2 >> garo2;
	visited.assign(N, vector<bool>(N, false));
	BFS();
	cout << resultCount;

}