알고리즘/BOJ(C++)
[백준 / BOJ] 1600 :: 말이 되고픈 원숭이
쿠마쿠마34
2020. 12. 30. 23:03
반응형
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
문제 설명:
- 시작 지점(제일 왼쪽, 제일 위 (H,1))에서 도착지점 (제일 오른쪽, 제일 아래(1,W))까지 이동하는 최단 거리를 찾자
- 이동할 수 있는 방법에는 두가지가 있다.
1. 체스판의 나이트 처럼 이동하는 경우(현 자리에서 8가지)
2. 인접한 칸으로 이동하는 경우(현 자리에서 4가지)
- 이 때 1번의 방법으로 이동하는 경우는 최대 K번까지 사용 가능하다.
풀이 / 구현 방법 :
- BFS
- BFS로 최단 거리를 업데이트 해 나갈 것인데, 이 때 dist[x][y][k] 배열을 사용한다. 이 배열은 x,y까지 1번 이동을 k번 사용하여 이동했을 때의 최단 거리이다.
- BFS로 구현할 때 queue에 넣어두고 꺼내면서 다음에 이동할 수 있는 곳을 탐색하는 로직은 동일하다. 이 이동가능한 로직을 찾는 과정에서 1번과 2번 이동할 수 있는 방법을 모두 구현하면 된다.
- 그리고 K번까지만 사용 가능하므로 현재 K번 사용 횟수 + 1 이 K를 넘으면 이 경우는 이동 불가능한 경우이다.
- 자세한 구현 내용은 소스로!
소스코드
더보기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <iostream> #include <queue> #define MAX 987654321 using namespace std; int dx[8] = { -2,-1,1,2,-2,-1,1,2 }; int dy[8] = { -1,-2,-2,-1,1,2,2,1 }; //말이 갈 수 있는 8가지 위치 int adj_x[4] = { -1,1,0,0 }; int adj_y[4] = { 0,0,-1,1 }; //인접해서 갈 수 있는 네 곳 int K, W, H; int map[201][201]; int dist[201][201][31];//dist[x][y][k] : x,y에 k번의 이동으로 도착할 수 있는 최소 횟수 int main() { cin >> K >> W >> H; for (int i = H; i >=1 ; i--) { for (int j = 1; j <= W; j++) { cin >> map[i][j]; } } //입력값이 H가 큰 순서로 들어옴을 유의(위에서 아래로 입력이 들어옴) for (int i = 0; i < 201; i++) { for (int j = 0; j < 201; j++) { for (int k = 0; k < 31; k++) { dist[i][j][k] = MAX; } } } //dist 값 초기화 queue<pair<pair<int, int>,int> > q; dist[H][1][0] = 0;//시작 지점 왼쪽 위 q.push({ { H,1 },0 }); while (!q.empty()) { int x = q.front().first.first; int y = q.front().first.second; int cnt = q.front().second; q.pop(); //말이 이동하듯이 이동 for (int k = 0; k < 8; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx <1 || nx > H || ny < 1 || ny > W || map[nx][ny] == 1) continue;//이동 불가능한 곳 if (dist[nx][ny][cnt + 1] > dist[x][y][cnt] + 1 && cnt + 1 <= K) { //나이트처럼 이동한 횟수가 K를 넘으면 이동 불가 dist[nx][ny][cnt + 1] = dist[x][y][cnt] + 1; q.push({ {nx,ny},cnt + 1 }); } } //인접한 곳 이동 for (int k = 0; k < 4; k++) { int nx = x + adj_x[k]; int ny = y + adj_y[k]; if (nx <1 || nx > H || ny < 1 || ny > W || map[nx][ny] == 1) continue;//이동 불가능한 곳 if (dist[nx][ny][cnt] > dist[x][y][cnt] + 1) { dist[nx][ny][cnt] = dist[x][y][cnt] + 1; q.push({ {nx,ny},cnt}); } } } int ans = MAX; for (int i = 0; i <= K; i++) { if (ans > dist[1][W][i]) ans = dist[1][W][i]; } if (ans == MAX) cout << "-1" << '\n'; else cout << ans << endl; } | cs |
반응형