출처 : https://www.acmicpc.net/problem/2206
벽 부수고 이동하기 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 10615 | 2012 | 1312 | 23.885% |
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이 때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이 때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
6 4 0100 1110 1000 0000 0111 0000
예제 출력 1
15
예제 입력 2
4 4 0111 1111 1111 1110
예제 출력 2
-1
풀이
대체적으로는 일반적인 bfs 문제 풀이 방식과 동일합니다.
다만, 이 경우에는 (a, b) 라는 위치에 있다고 가정했을 때, 해당 위치에 갔었다는 것을 기록하는 배열이 필요합니다.
해당 위치를 방문했었다는 것을 기록 할 때, 벽을 한 번 부수고 갔었던 곳과
벽을 안 부수고 갔었던 기록을 저장하는 배열 2개를 만들어서 각각 저장했습니다.
그리고 현재 위치의 주변 4방향을 기준으로 다시 살펴봅니다.
살펴보는 위치의 인덱스에 벽이 없으면 현재 벽을 부순 상태를 유지하면서 다음 queue 로 넘깁니다.
살펴보는 위치의 인데스에 벽이 있으면 현재 벽을 부순 상태가 아니면 벽을 부순 상태로 만들어서 다음 queue로 넘깁니다.
살펴보는 위치의 인데스에 벽이 있으면 현재 벽을 부순 상태이면 생략합니다.
자세한 내용은 소스코드를 참조해주세요~
소스코드
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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <iostream> #include <vector> #include <queue> #pragma warning(disable:4996) using namespace std; #define SIDE 4 int side_arr[SIDE][2] = { {-1,0},{0,1},{1,0},{0,-1} }; // 상우하좌 // BFS_Q 에는 한 번이라도 파괴를 했는지에 대한 여부, 인덱스, 깊이를 저장 typedef struct BFS_Q { int is_crashed_; int row_; int col_; }BFS_Q; int main(){ int N, M; scanf("%d %d", &N, &M); vector<vector<int>> map(N + 1, vector<int>(M + 1)); vector<vector<int>> is_visited_crash(N + 1, vector<int>(M + 1, 0)); vector<vector<int>> is_visited_non_crash(N + 1, vector<int>(M + 1, 0)); for(int n_idx = 1; n_idx <= N; n_idx++) for (int m_idx = 1; m_idx <= M; m_idx++) scanf("%1d", &map[n_idx][m_idx]); BFS_Q start_Q = { 0, 1, 1 }; int bfs_size = 1; int bfs_depth = 0; queue<BFS_Q> bfs_queue; bfs_queue.push(start_Q); while (true) { // go next depth if (bfs_size == 0) { if (bfs_queue.size() == 0) break; bfs_size = bfs_queue.size(); bfs_depth++; } BFS_Q front_Q = bfs_queue.front(); bfs_queue.pop(); bfs_size--; /* printf("%d %d %d\n", front_Q.is_crashed_, front_Q.row_ , front_Q.col_);*/ // 정답 인덱스이면 그냥 종료 if (front_Q.row_ == N && front_Q.col_ == M) { printf("%d", bfs_depth + 1); return 0; } // 만약에, 이 경로가 crash 를 한 번 했던 녀석이라면 crash 를 했던 map의 값을 살펴본다. // 방문 했던 노드에서 부쉈던 경험이 있을때, 값이 더 작거나 같은 요소가 있으면 그냥 넘긴다. // crash 를 하지 않은 녀석도 위와 같은 동일한 논리로 진행한다. if (front_Q.is_crashed_ == 0) { if (is_visited_non_crash.at(front_Q.row_).at(front_Q.col_)) continue; else is_visited_non_crash.at(front_Q.row_).at(front_Q.col_) = 1; } else { if (is_visited_crash.at(front_Q.row_).at(front_Q.col_)) continue; else is_visited_crash.at(front_Q.row_).at(front_Q.col_) = 1; } // 현재노드의 4 방향 옆을 살핀다. for (int side_idx = 0; side_idx < SIDE; side_idx++) { int now_row = front_Q.row_ + side_arr[side_idx][0]; int now_col = front_Q.col_ + side_arr[side_idx][1]; // 범위 체크 if (!(1 <= now_row && now_row <= N)) continue; if (!(1 <= now_col && now_col <= M)) continue; // 만약, 다음 노드의 부분이 벽이 아니라면 그냥 추가 if (map.at(now_row).at(now_col) == 0) { if (is_visited_non_crash.at(now_row).at(now_col)) continue; BFS_Q plus_Q = { front_Q.is_crashed_ , now_row , now_col}; bfs_queue.push(plus_Q); } // 만약, 해당 위치가 벽이고 현재의 crash 가 1이 아니면 1로 변경하고 넘긴다. else if (front_Q.is_crashed_ == 0) { if (is_visited_crash.at(now_row).at(now_col)) continue; BFS_Q plus_Q = { 1, now_row , now_col}; bfs_queue.push(plus_Q); } // 만약, 해당 위치가 벽이고 현재의 crash 가 1이면 그냥 continue; else { continue; } } } printf("-1"); return 0; } | cs |