[BOJ] 1600. 말이 되고픈 원숭이

* 최단 거리가 정답이 아닐 수도 있다. 

*

1
3 5
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0

 

처럼 도착 지점이 장애물로 막혀져있는 경우 

0 0 0 x 0
0 0 x 0 1
0 0 0 1 0

 

x로 표시되어있는 지점까지 원숭이로 이동한 후 말의 이동을 하는 방법이 도착할 수 있는 최선의 방법이다.

 

* 큐에는 4가지 값이 들어간다. 

{움직인 횟수, 말로 움직인 횟수, 좌표}

말로 움직인 횟수가 k보다 작을때까지만 말로 움직인 좌표를 큐에 넣을 수 있다. 

원숭이로 움직인 횟수는 항상 넣는다. (최단 경로 != 정답)

 

*코드가 깔끔하지 않다.

 

*dx / dy => 상하좌우

cdx / cdy => 대각선 

 

 

#include <iostream> #include <vector> #include <queue> #define INF 987654321 using namespace std; int k, n, m; int map[202][202]; typedef pair<int, int> pp; typedef pair<pp, pp> pppp; bool visited[202][202][31]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int cdx[4] = {-1, -1, 1, 1}, cdy[4] = {-1, 1, -1, 1}; int ans = INF; bool checkRange(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) return false; return true; } void bfs() { queue<pppp> q; q.push(pppp(pp(0, 0), pp(0, 0))); visited[0][0][0] = 1; //원숭이가 움직인 횟수를 저장한다. //만약, 이 자리에 도착했을 때 이보다 더 많은 이동횟수가 필요하다면 이동하지 않는다.?? while (!q.empty()) { int size = q.size(); while (size--) { int cnt = q.front().first.first; int cntH = q.front().first.second; //말의 움직임 int x = q.front().second.first; int y = q.front().second.second; q.pop(); if (x == n - 1 && y == m - 1) { ans = ans > cnt ? cnt : ans; return; } //말은 장애물을 뛰어넘을 수 있다. if (cntH < k) { for (int i = 0; i < 4; i++) { //말 형태로 움직일 수 있다. int nx = x + cdx[i]; int ny = y + cdy[i]; if (checkRange(nx, ny)) { //이 대각선 좌표를 기준으로 if (i == 0) { if (checkRange(nx + dx[0], ny + dy[0]) && !visited[nx + dx[0]][ny + dy[0]][cntH + 1] && !map[nx + dx[0]][ny + dy[0]]) { visited[nx + dx[0]][ny + dy[0]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[0], ny + dy[0]))); } if (checkRange(nx + dx[2], ny + dy[2]) && !visited[nx + dx[2]][ny + dy[2]][cntH + 1] && !map[nx + dx[2]][ny + dy[2]]) { visited[nx + dx[2]][ny + dy[2]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[2], ny + dy[2]))); } } if (i == 1) { if (checkRange(nx + dx[0], ny + dy[0]) && !visited[nx + dx[0]][ny + dy[0]][cntH + 1] && !map[nx + dx[0]][ny + dy[0]]) { visited[nx + dx[0]][ny + dy[0]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[0], ny + dy[0]))); } if (checkRange(nx + dx[3], ny + dy[3]) && !visited[nx + dx[3]][ny + dy[3]][cntH + 1] && !map[nx + dx[3]][ny + dy[3]]) { visited[nx + dx[3]][ny + dy[3]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[3], ny + dy[3]))); } } if (i == 2) { if (checkRange(nx + dx[1], ny + dy[1]) && !visited[nx + dx[1]][ny + dy[1]][cntH + 1] && !map[nx + dx[1]][ny + dy[1]]) { visited[nx + dx[1]][ny + dy[1]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[1], ny + dy[1]))); } if (checkRange(nx + dx[2], ny + dy[2]) && !visited[nx + dx[2]][ny + dy[2]][cntH + 1] && !map[nx + dx[2]][ny + dy[2]]) { visited[nx + dx[2]][ny + dy[2]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[2], ny + dy[2]))); } } if (i == 3) { if (checkRange(nx + dx[1], ny + dy[1]) && !visited[nx + dx[1]][ny + dy[1]][cntH + 1] && !map[nx + dx[1]][ny + dy[1]]) { visited[nx + dx[1]][ny + dy[1]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[1], ny + dy[1]))); } if (checkRange(nx + dx[3], ny + dy[3]) && !visited[nx + dx[3]][ny + dy[3]][cntH + 1] && !map[nx + dx[3]][ny + dy[3]]) { visited[nx + dx[3]][ny + dy[3]][cntH + 1] = 1; q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[3], ny + dy[3]))); } } } } } for (int j = 0; j < 4; j++) { //원숭이 움직임 int cx = x + dx[j]; int cy = y + dy[j]; if (checkRange(cx, cy) && !visited[cx][cy][cntH] && !map[cx][cy]) { visited[cx][cy][cntH] = 1; q.push(pppp(pp(cnt + 1, cntH), pp(cx, cy))); } } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> k >> m >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } bfs(); if (ans == INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }