1. 구현이 더 중요한 문제.
2. 그냥 시작 + 각 더러운 곳(DT) 에서 다른 DT로의 최소 거리를 저장한 2차원 배열을 BFS로 만들고
3. 시작부터 모든 경로를 탐색하여 최소 거리를 뽑아내면 됨.
4. 방문 할 수 없는지 판별은 시작에서 갈 수 없는 DT가 있는지 확인하면 됨
구현
1. 거리 저장한 2차원 배열은, 최대 DT가 10개이므로 [11][11] 로 선언함
이때, 0은 시작장소를 뜻함
따라서 각 줄의 0번째 칸과 자기자신은 0이어야함
2. 시작하는 곳과 DT의 위치를 배열에 저장함.
3. 맵에서 시작하는 곳은 '0' 으로, 나머지 각 DT는 '0' + 2. 배열 상의 index 로 BFS시 바로바로 참조가능하게 한다.
코드
#include <iostream>#include <cstring>#define MAX_WIDTH 20using namespace std;typedef struct Location { int row; int col; int length;} Location;int w, h, numOfD = 1, eachOther[11][11];char map[MAX_WIDTH][MAX_WIDTH];Location q[MAX_WIDTH * MAX_WIDTH], node[11];bool visit[MAX_WIDTH][MAX_WIDTH], visitDistance[11];void BFS(Location s);int minDistance(int d, int cur);int min(int a, int b) { return a < b ? a : b;}int main() { while (true) { cin >> w >> h; if (w == 0 && h == 0) break; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { cin >> map[i][j]; if (map[i][j] == 'o') { map[i][j] = '0'; // start는 0, 더티는 1~10 node[0] = { i, j }; } else if (map[i][j] == '*') { node[numOfD] = { i, j }; map[i][j] = '0' + numOfD++; } } for (int i = 0; i < numOfD; i++) BFS(node[i]); int count = 0; for (int i = 1; i < numOfD; i++) if (eachOther[0][i] > 0) count++; if (count < numOfD - 1) cout << -1 << endl; else cout << minDistance(0, 0) << endl; numOfD = 1; memset(eachOther, 0, sizeof(eachOther)); }}void BFS(Location s) { //start면 0, 더러운 곳이면 1~10 들어감 int cur = map[s.row][s.col] - '0'; int length = 0, index = 0; q[length++] = { s.row, s.col, 0 }; visit[s.row][s.col] = true; while (index < length) { int row = q[index].row, col = q[index].col, l = q[index++].length; if (map[row][col] - '0' >= 1 && map[row][col] - '0' <= 10) { eachOther[cur][map[row][col] - '0'] = l; } if (row > 0 && !visit[row - 1][col] && map[row - 1][col] != 'x') { q[length++] = { row - 1,col, l + 1 }; visit[row - 1][col] = true; } if (row < h - 1 && !visit[row + 1][col] && map[row + 1][col] != 'x') { q[length++] = { row + 1,col, l + 1 }; visit[row + 1][col] = true; } if (col > 0 && !visit[row][col - 1] && map[row][col - 1] != 'x') { q[length++] = { row,col - 1, l + 1 }; visit[row][col - 1] = true; } if (col < w - 1 && !visit[row][col + 1] && map[row][col + 1] != 'x') { q[length++] = { row, col + 1, l + 1 }; visit[row][col + 1] = true; } } for (int i = 0; i < length; i++) visit[q[i].row][q[i].col] = false;}int minDistance(int d, int cur) { int result = 2000000000; bool check = true; for (int i = 1; i < numOfD; i++) { if (!visitDistance[i]) { visitDistance[i] = true; result = min(result, minDistance(d + eachOther[cur][i], i)); visitDistance[i] = false; check = false; } } if (check) return d; else return result;}