[최단거리] 데스 나이트 16948

문제 해설 및 주의사항

1.  데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

 

2. 데스 나이트는 체스판 밖으로 벗어날 수 없다

 

3. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

 

---

 

풀이

1. 왜 bfs 인가?

 

a. 최소 이동 횟수를 구한다.

b. 한 번 이동 시, 한 번의 이동 횟수가 올라간다. 즉, 가중치가 1이다.

c. 도착점, 시작점 존재

d. 최악의 경우 O(N^2) 인데, N 의 최대가 200이므로 충분하다.

 

2. 비슷한 bfs 최단 거리 문제

---

풀이코드

#include <iostream>
#include <queue>
// tie 사용
#include <tuple>
using namespace std;

// x : 행 y : 열
// 말이 움직일 수 있는 경우들
int dx[] = {-2, -2, 0, 0, 2, 2};
int dy[] = {-1, 1, -2, 2, -1, 1};
int dist[200][200];

int main(){
	int n;
	cin >> n;
	// 시작점 x, y / 끝점 x, y
	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;
	
	// dist 배열 초기화
	fill_n(&dist[0][0], 200*200, -1);
	
	// bfs 시작 처리
	dist[sx][sy] = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	
	// bfs 시작
	while(!q.empty()){
		int x, y;
		tie(x, y) = q.front(); q.pop();
		// 다음 좌표 6개에 대해서 탐색
		for(int k = 0; k < 6; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			
			// 범위 체크
			if(0 <= nx && nx < n && 0 <= ny && ny < n){
				// 아직 미방문이라면
				if(dist[nx][ny] == -1){
					q.push(make_pair(nx, ny));
					dist[nx][ny] = dist[x][y] + 1;
				}
			}
		}
	}
	printf("%d\n", dist[ex][ey]);
}

 

---

퇴고

1. 문제 풀이 과정

 

a. bfs 최단거리 문제임을 파악한다.

b. 현재노드를, 다음 노드를 어떻게 표현할 것인지 생각한다. 그리고, 둘 사이의 관계를 어떻게 구현할 것인지 생각한다.

c. 최단거리를 어떻게 표현할 것인지 생각한다.

d. bfs 을 실시한다.