어흥
[백준 1600] 말이 되고픈 원숭이 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/1600
1. 주의할 점
- 같은 지점에 도착하더라고 나이트 이동 N번을 통해 도착한 지점과 나이트 이동 M번을 통해 도착한 지점을 구분해야 한다(N!=M)
2. 구현
- Check[][][] : Y,X,KnightJump 횟수 순으로 입력한다
- BFS를 통해 밑의 2가지 조건중 1개라도 만족하면 이동한다.
- 다음 이동지점이 배열범위 안이며 일반 이동인 경우 장애물 or 이미 같은 횟수의 나이트 이동을 통해 도착한 지점을 제외하고는 이동한다
- 다음 이동지점이 배열범위 안이며 나이트 이동횟수가 남아있으며 도착지점이 장애물 or 이미 기존 횟수 +1회의 나이트 이동을 통해 도착한 지점을 제외하고는 이동한다.
#define MAX 987654321
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int arr[200][200];
int check[200][200][31];
int dx[12] = { 0,1,0,-1,1,2,2,1,-1,-2,-2,-1 };
int dy[12] = { -1,0,1,0,-2,-1,1,2,2,1,-1,-2 };
int num, row, col;
int result = 0;
struct info {
int y, x, jump;
};
info tmp;
queue<info> q;
int main() {
cin >> num >> col >> row;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
for (int k = 0; k < 31; k++)
check[i][j][k] = MAX;
}
q.push({ 0,0,0});
check[0][0][0] = 0;
int result = 987654321;
while (!q.empty()) {
int cx = q.front().x;
int cy = q.front().y;
int cj = q.front().jump;
q.pop();
if (cx == col - 1 && cy == row - 1) {
result = check[cy][cx][cj];
break;
}
for (int i = 0; i < 12; i++) {
if (cj == num && i == 4) break; //남은 나이트 이동횟수가 없는 경우
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= 0 && ny >= 0 && nx < col && ny < row) {
if (arr[ny][nx] == 1) continue; //이동 + 다음칸이 장애물
if (i < 4) {
if (check[ny][nx][cj] <= check[cy][cx][cj] + 1) continue;
q.push({ ny,nx,cj });
check[ny][nx][cj] = check[cy][cx][cj] + 1;
}
else { //나이트 점프
if (check[ny][nx][cj + 1] <= check[cy][cx][cj] + 1) continue;
q.push({ ny,nx,cj + 1 });
check[ny][nx][cj + 1] = check[cy][cx][cj] + 1;
}
}
}
}
if (result == MAX) result = -1;
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 18809] Gaaaaaaaaaarden (C++) (0) | 2020.03.21 |
---|---|
[백준 18808] 스티커 붙이기 (C++) (2) | 2020.03.21 |
[백준 13913] 숨바꼭질 4 (C++) (0) | 2020.03.19 |
[백준 5567] 결혼식 (C++) (0) | 2020.03.19 |
[백준 3678] 카탄의 개척자 (C++) (3) | 2020.03.18 |
Comments