👀 문제 설명
게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.
크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.
데스 나이트는 체스판 밖으로 벗어날 수 없다.
입력
첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.
출력
첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.
예제 입력 1
7
6 6 0 1
예제 출력 1
4
예제 입력 2
6
5 1 0 5
예제 출력 2
-1
예제 입력 3
7
0 3 4 3
예제 출력 3
2
✍🏻풀이
큐를 사용한 BFS 문제이다.
dx, dy를 사용해 갈 수 있는 방향을 저장해둔다. 현재 위치를 큐에 넣고, 큐가 빌 때까지 이동한다.
chess 배열에 위치까지의 거리를 저장하고, visit 배열을 사용해 이미 방문한 위치인지 판별한다.
코드
#include <stdio.h>
#include <iostream>
#include <queue>
#define MAX 200
using namespace std;
int dx[6] = { -2, -2, 0, 0, 2, 2 };
int dy[6] = { -1, 1, -2, 2, -1, 1 };
int chess[MAX][MAX];
int visit[MAX][MAX];
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
chess[i][j] = MAX;
}
}
queue<pair<int, int>> Q;
Q.push({ r1, c1 });
chess[r1][c1] = 0;
visit[r1][c1] = 1;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
int curX = cur.first;
int curY = cur.second;
for (int dir = 0; dir < 6; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N)
continue;
if (!visit[nextX][nextY]) {
visit[nextX][nextY] = 1;
chess[nextX][nextY] = chess[curX][curY] + 1;
Q.push({ nextX, nextY });
}
}
}
if (visit[r2][c2] == 0) {
cout << "-1" << "\n";
}
else {
cout << chess[r2][c2] << "\n";
}
return 0;
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Baekjoon] 일곱 난쟁이 (0) | 2021.02.28 |
---|---|
[Baekjoon] 정수 삼각형 (0) | 2021.02.27 |
[Baekjoon] ⚾️ (0) | 2021.02.25 |
[SWEA] 지그재그 숫자 (2) | 2021.02.25 |
[Baekjoon] 수 이어 쓰기 1 (0) | 2021.02.24 |