백준 16948. 데스 나이트

알고리즘 중급 문제 중 611 - BFS(연습)

데스 나이트

1. 간단 설명

---

나이트의 이동과 유사한 문제

나이트가 8방향으로 움직인다면

데스 나이트는 6방향으로 움직일 수 있다

.X.X.
.....
X.O.X
.....
.X.X.

O가 현위치
X가 이동 가능한 경로

시작 좌표와 도착 좌표가 주어졌을 때, 최소 이동 회수를 구하는 문제

예시

---

7
6 6 0 1

7칸짜리 배열 (6,6)에서 (0,1)로 이동하는 회수

.......
.......
.......
.......
.......
.......
......O

.......
.......
.......
.......
.....1.
.......
......X

.......
.......
....2..
.......
.....X.
.......
......X

...3...
.......
....X..
.......
.....X.
.......
......X

.4.X...
.......
....X..
.......
.....X.
.......
......X

4번만에 도달 할 수 있다

3. 알고리즘

---

너비 우선 탐색을 이용하여 경로를 계산한다

2차원 최단 경로를 묻는 문제는 대부분 BFS인듯함(아닐수도)

1. N과 시작, 도착 좌표를 입력받는다
2. 시작 좌표를 BFS 시작 큐에 넣고, BFS를 시작한다
3. 데스 나이트가 이동 가능한 경로를 체크한다
	3-1. 이동 가능한 경로가 목적지라면, 몇번 움직였는지 출력 후 종료한다
	3-2. 만약 방문한 적이 있다면 패스
	3-3. 맵 밖이라면 패스
	3-4. 위 조건들을 통과했다면, 방문 처리 후 큐에 넣는다
4. 큐를 다 돌았다면, 목적지에 도달하지 못한것이므로 -1을 출력하고 종료한다

필요 변수

• 체스판의 크기 int N(5 ≤ N ≤ 200)
• 체스판의 방문 정보를 저장할 int map[201][201] 방문했다면 이전 스텝에 +1을 해서 저장
• 시작 좌표와 도착 좌표
• BFS 탐색을 위한 큐
• 데스 나이트가 이동 가능한 경로 direct[6][2]

4. 소스코드

---

#include <iostream>
#include <queue>

using namespace std;

int N;
int map[201][201]; // 방문처리 겸, 스텝 수 저장

int direct[6][2] = {
	{-2,-1},
	{-2,+1},
	{0,-2},
	{0,+2},
	{2,-1},
	{2,+1}
};

struct pos {
	int y;
	int x;
};

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
    // 1. Input
	cin >> N;
	int y1, x1, y2, x2;
	cin >> y1 >> x1 >> y2 >> x2;

    // 2. BFS
	queue<pos> qu;
	qu.push({ y1, x1 });
	map[y1][x1] = 1; 

	while (!qu.empty()) {
		pos now = qu.front();
		qu.pop();

		for (int t = 0; t < 6; t++) {
			int dy = now.y + direct[t][0];
			int dx = now.x + direct[t][1];

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue; // 경계 체크
			if (map[dy][dx] != 0) continue; // 방문 체크
			if (dy == y2 && dx == x2) { // 도착지 체크
				cout << map[now.y][now.x];
				return 0;
			}
            // 큐에 넣기
			map[dy][dx] = map[now.y][now.x] + 1;
			qu.push({ dy, dx });
		}
	}
	cout << -1;

	return 0;
}

다른 사람의 코드를 볼 수 있었는데

나는 int map[201][201]과 같은 고정형 크기의 2차원 배열을 사용한 반면,

그 사람은 unordered map을 이용해 체스판의 크기를 동적으로 사용하였다.

BFS를 처음 학습할 때, 맵의 크기를 고정형으로 설정하는 것이

1. 메모리가 연속적으로 할당되기 때문에 접근속도가 빠르다
2. 코드 작성이 간단하고, 직관적이라 이해하기 쉬움
3. 크기가 고정되어있어, 메모리 계산이 쉬움

위 이유로 이런식으로 할당하는것이 좋다고 배웠다.

그런데 잘 생각해보면

1. 필요한 크기 이상의 메모리 크기를 할당함
2. 스택 메모리를 사용하기 때문에, 배열이 매우 큰 경우 스택오버플로우 발생 가능

즉, 메모리의 크기 때문에 문제가 될 수 있다

unordered map을 사용한 희소 배열(Spares Array)은 해시맵을 이용하여

실제로 값이 존재하는 좌표만 저장하여 메모리를 효율적으로 사용할 수 있기 때문에

매우 큰 공간을 필요하는 배열에서도 유용하게 사용할 수 있다

공간을 다루는 다양한 방법이 있기 때문에, 나중에 이를 한번 다뤄봐야겠다.