집배원 한상덕

*피로도를 최소부터 최대까지 하나의 배열로 저장한 후 투포인터를 사용해서 모든 집을 순회했을 때의 차이를 구한다. 

*우체국으로 돌아왔을 때까지의 최단 경로를 구하는 게 아니기 때문에 굳이 다시 P로 돌아올 필요가 없다. (이거 중요!)

*K개 만큼의 집을 들렀을 때 최소 피로도를 구하면 된다. 

#include <iostream> #include <vector> #include <queue> #include <set> #include <cstring> using namespace std; int n, house = 0; char map[51][51]; int tired[51][51]; bool visited[51][51]; vector<int> v; typedef pair<int, int> pp; typedef pair<pp, pp> pppp; pp start; int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; void bfs() { int ans = 987654321; int left = 0, right = 0; //피로도의 값을 비교한다. while (left <= right && right < v.size()) { int cnt = 0; //cnt == house면 모든 집을 다 들린 것이다. //갈 수 있는 곳이면 left++ //없으면 right++; queue<pp> q; memset(visited, 0, sizeof(visited)); if (v[left] <= tired[start.first][start.second] && tired[start.first][start.second] <= v[right]) { q.push(start); visited[start.first][start.second] = true; } // cout <<"D1 " << left << " " << right << '\n'; while (!q.empty()) { int x = q.front().first; //지금까지의 누적 피로도 int y = q.front().second; q.pop(); for (int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue; if (tired[nx][ny] < v[left] || tired[nx][ny] > v[right]) continue; if (map[nx][ny] == 'K') { cnt++; } visited[nx][ny] = true; q.push(pp(nx, ny)); } } // cout << "D2 " << cnt << " " << house << '\n'; if (cnt == house) { ans = min(v[right] - v[left], ans); left++; } else right++; } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; if (map[i][j] == 'P') start = pp(i, j); else if (map[i][j] == 'K') house++; } } set<int> t; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> tired[i][j]; t.insert(tired[i][j]); } } set<int>::iterator it; for (it = t.begin(); it != t.end(); it++) { v.push_back(*it); // cout << *it << '\n'; } bfs(); return 0; }