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

[최단거리] 데스 나이트 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 #include // tie 사용 #include 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> 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

", dist[ex][ey]); }

퇴고

1. 문제 풀이 과정

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

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

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

d. bfs 을 실시한다.

반응형

from http://private-k.tistory.com/183 by ccl(A) rewrite - 2021-10-23 16:26:21