4991번 - 로봇 청소기
문제에서 쓰레기의 값이 10개 이하이고, 맵에서 vertex 의 최대 갯수가 400개가 된다는 것을 파악하였다. 따라서 플로이드 워셜 알고리즘은
시간 복잡도가 O(N^3) 이고 , 400^3 은 6천만정도 되기 때문에 가능하다고 생각하고 문제를 풀었다. 하지만 이 문제는 독특하게도 테스트케
이스가 while문을 통해서 한꺼번에 여러개가 실행되므로 최대 6천만을 여러번 돌리다보면 시간초과가 발생하게 된다. 따라서 이제는 각 쓰레
기마다 BFS를 이용해서 로봇,쓰레기들의 최소거리의 모든 쌍을 구해야 했다.
따라서 dirt 라는 벡터에 로봇의 위치와 쓰레기들의 위치를 모두 저장해주었다. 그 다음 for문을 이용해서 모든 쓰레기들에서 BFS를 돌리고,
다른 쓰레기들과의 거리를 D라는 배열에 담았다. (D의 4차원 배열을 쓰기가 싫어서, x,y좌표를 하나의 노드 값으로 변화시켰다)
그러면 이제 주어진 D를 이용하여 순열을 구성하면 된다. 쓰레기들간의 거리 순열로 나타내고 그 중에서 최솟값을 구하면 된다. 이 과정은 쓰
레기가 최대 10개밖에 되지 않기 때문에 10!의 작은 수로 쉽게 구할 수 있다. 여기서 백트래킹을 활용하기 위해 dirt 벡터를 구성할 때, 좌표말
고도 하나의 값을 더 추가해서 재귀함수에서 백트래킹 용도로 활용하였다.
### 계속해서 틀렸던 점 ###
처음에 트러블슈팅 과정에서 못 찾았던 점은,
if (ans >= INF)
ans = -1;
이 부분이었는데, 처음에는 INF=987654321로 if(ans>=INF) 로 조건문을 설정했었다. 하지만 자칫 잘못하다가 덧셈과정에서 오버플로우가
발생하여 계속 오답처리 되는 부분이 있었다. 평상시 습관처럼 그냥 엄청 큰 수로 해줬는데 이게 오히려 잘못된 점이었다. 그래서 혹시 쓰레
기끼리의 거리 10개 * INF 값이 int형 변수의 범위를 넘지 않아야 하므로 INF 를 변경해주었다.
<정답 코드 - BFS >
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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | #include<iostream> #include<vector> #include<queue> #include<algorithm> #define INF 10000000 using namespace std; int N, M; int ans; int sx, sy; char map[20][20]; int D[400][400]; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; vector<pair<int,pair<int, int>>> dirt; void init() { // 벡터 초기화 dirt.clear(); // D값 초기화 for (int i = 0; i < 400; i++) { for (int j = 0; j < 400; j++) { D[i][j] = INF; } } // 맵 초기화 for (int i = 0; i < 20; i++) { for (int j = 0; j < 20; j++) { map[i][j] = 'x'; } } } void go(int k,int now, int sum) { if (k == dirt.size()) { if (sum < ans) ans = sum; return; } for (int i = 0; i < dirt.size(); i++) { int x = dirt[i].second.first; int y = dirt[i].second.second; int next = x * M + y; if (dirt[i].first == 0) { dirt[i].first = 1; go(k + 1, next, sum + D[now][next]); dirt[i].first = 0; } } } int main() { //freopen("input.txt", "r", stdin); while (true) { ans = INF; cin >> M >> N; if (M == 0 && N == 0) break; init(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> map[i][j]; if (map[i][j] == '*') dirt.push_back({ 0,{i,j} }); if (map[i][j] == 'o') { sx = i, sy = j; dirt.push_back({ 1,{i,j} }); } } } // BFS를 이용해서 모든 쓰레기들끼리의 최소거리 쌍 구하기 for (int i = 0; i < dirt.size(); i++) { queue<pair<int, int>> q; int dist[20][20] = { 0, }; int curx = dirt[i].second.first; int cury = dirt[i].second.second; int cur = curx * M + cury; dist[curx][cury] = 1; q.push({ curx,cury }); while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); if (map[x][y] == '*' || map[x][y]=='o') { int next = x * M + y; D[cur][next] = dist[x][y] - 1; } for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] != 'x' && dist[nx][ny] == 0) { dist[nx][ny] = dist[x][y] + 1; q.push({ nx,ny }); } } } } // 쓰레기가 존재하는 부분 순열로 최솟값 구하기 // 청소시가 처음 놓여있는 위치는 첫번째로 고정 int cur = sx * M + sy; go(1,cur, 0); if (ans >= INF) ans = -1; cout << ans << endl; } return 0; } | cs |
<정답 코드 - 시간초과 (플로이드 와샬)>
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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | #include<stdio.h> #include<vector> #include<algorithm> #define INF 987654321 using namespace std; int N, M; int ans; char map[20][20]; int D[400][400]; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; vector<pair<int,pair<int, int>>> dirt; void init() { // 벡터 초기화 dirt.clear(); // D값 초기화 for (int i = 0; i < 400; i++) { for (int j = 0; j < 400; j++) { D[i][j] = INF; } } // 맵 초기화 for (int i = 0; i < 20; i++) { for (int j = 0; j < 20; j++) { map[i][j] = 'x'; } } } void go(int k,int now, int sum) { if (k == dirt.size()) { if (sum < ans) ans = sum; return; } for (int i = 0; i < dirt.size(); i++) { int x = dirt[i].second.first; int y = dirt[i].second.second; int next = x * M + y; if (dirt[i].first == 0) { dirt[i].first = 1; go(k + 1, next, sum + D[now][next]); dirt[i].first = 0; } } } int main() { //freopen("input.txt", "r", stdin); while (true) { ans = INF; int sx, sy; scanf("%d %d", &M, &N); //cin >> M >> N; if (M == 0 && N == 0) break; init(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { //cin >> map[i][j]; scanf(" %c", &map[i][j]); if (map[i][j] == '*') dirt.push_back({ 0,{i,j} }); if (map[i][j] == 'o') sx = i, sy = j; } } // 연결할 수 있는 노드들 연결 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int now = i * M + j; for (int d = 0; d < 4; d++) { int ni = i + dx[d]; int nj = j + dy[d]; int next = ni * M + nj; if (ni >= 0 && nj >= 0 && ni < N && nj < M && map[ni][nj] != 'x') { D[now][next] = 1; } } } } //플로이드와셜 for (int k = 0; k < N*M; k++) { for (int i = 0; i < N*M; i++) { for (int j = 0; j < N*M; j++) { D[i][j] = min(D[i][j], D[i][k] + D[k][j]); } } } int cur = sx * M + sy; // 쓰레기가 존재하는 부분 순열로 최솟값 구하기 go(0,cur, 0); if (ans == INF) ans = -1; printf("%d\n", ans); } return 0; } | cs |
반응형