2일간의 휴식아닌 휴식을 가진 후 풀어본 문제는 BOJ 21278 호석이 두마리 치킨 이다!
완전 탐색 문제로 생각하고 시작했으나 플로이드와샬까지 함께 사용해 볼 수 있었다!
BOJ 21278 호석이 두마리 치킨
컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다.
이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.
키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.
컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.
입출력
나의 풀이
크게 세 단계로 나누어 풀이를 진행하였다.
가능한 경우의 수 구하기 + 각 경우마다의 최소 왕복 거리 구하기 + 정렬 후 가장 짧은 경우 구하기
1. 가능한 경우의 수 구하기
예제 입력의 경우로 설명하자면 1~5까지의 5개의 건물 중 2개의 치킨집을 고르는 경우의 수를 말한다. 5개 중 2개를 뽑는 경우의 수 이다.
<algorithm> 헤더의 next_permutation 을 이용해서 가능한 모든 조합 combinations 를 구하였다.
combination 코드
vector<pair<int, int>> getCombinations(int n) {
vector<pair<int, int>> combinations;
vector<bool> select;
for (int i = 0; i < n-2; ++i) {
select.push_back(false);
}
select.push_back(true);
select.push_back(true);
do{
bool first = false;
pair<int, int> combi;
for (int i = 0; i < n; ++i) {
if (select[i]) {
if (!first) {
first = true;
combi.first = i+1;
}else{
combi.second = i+1;
combinations.push_back(combi);
break;
}
}
}
}while (next_permutation(select.begin(), select.end()));
return combinations;
}2. 각 경우마다의 최소 왕복 거리 구하기
1번에서 구한 combinations 를 대상으로 각 조합마다 치킨집 까지의 최소 왕복 거리를 계산한다.
이 과정에서 난 처음에 BFS를 사용하여 구하였는데 이 과정에서 시간초과가 날 수도 있을 것 같았다. combinations[i] 마다 같은 지도 상에서 BFS 를 수행하기 때문에 중복되는 부분이 있을 것이라 생각했다.
처음 제출했을 때, 정확히 시간초과 때문인지는 모르겠지만 통과해야 하는 19개의 테스트 케이스 중 7개까지만 맞는 부분성공을 받았고 이후에 FloydWarshall 알고리즘을 사용하여 코드를 수정하였다.
FloydWarshall 적용 코드
void floydWarshall(vector<vector<int>> & shortest) {
for (int k = 1; k <= N ; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (shortest[i][j] > shortest[i][k] + shortest[k][j]){
shortest[i][j] = shortest[i][k] + shortest[k][j];
}
}
}
}
}FloydWarshall 알고리즘을 사용하여 한 노드에서 다른 노드로 가는 최소 경로를 미리 계산하여 map을 갱신하고, 계산된 map의 값을 가져다 쓰면서 매번 계산해 주는 과정을 생략할 수 있었다! 또 메모리적인 측면에서도 훨씬 이득일 것이다!
이 과정을 통해 '각 치킨집 조합 & 각 조합 combinations[i] 마다의 최소 왕복 거리 값'을 묶어 배열 candidates 에 넣어주었다.
3. 정렬 후 가장 짧은 경우 구하기
이후 완성된 배열 candidates 를 정해진 기준대로 정렬한다.
<algorithm> 헤더의 sort 함수를 이용하였고 비교 기준을 따로 정의해 정렬하였다.
정렬 기준 코드
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
if (a.second == b.second){
if (a.first.first == b.first.first){
return a.first.second < b.first.second;
}else{
return a.first.first < b.first.first;
}
}else{
return a.second<b.second;
}
}마지막으로 정렬된 candidates 의 가장 앞에 있는 원소 candidates[0] 을 정답으로 출력하였다.
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 100000
// BOJ 21278 호석이 두마리 치킨, 골드 5, Folyd Warshall & Brute Force
using namespace std;
int N;
vector<vector<int>> map;
// [ 각 경우의 조합 - 최소 왕복거리 ] 배열 정렬 기준
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
if (a.second == b.second){
if (a.first.first == b.first.first){
return a.first.second < b.first.second;
}else{
return a.first.first < b.first.first;
}
}else{
return a.second<b.second;
}
}
// 가능한 모든 경우의 수 구하기
vector<pair<int, int>> getCombinations(int n) {
vector<pair<int, int>> combinations;
vector<bool> select;
for (int i = 0; i < n-2; ++i) {
select.push_back(false);
}
select.push_back(true);
select.push_back(true);
do{
bool first = false;
pair<int, int> combi;
for (int i = 0; i < n; ++i) {
if (select[i]) {
if (!first) {
first = true;
combi.first = i+1;
}else{
combi.second = i+1;
combinations.push_back(combi);
break;
}
}
}
}while (next_permutation(select.begin(), select.end()));
return combinations;
}
// 플로이드 와샬 - 각 노드까지의 최소 거리 계산
void floydWarshall(vector<vector<int>> & shortest) {
for (int k = 1; k <= N ; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (shortest[i][j] > shortest[i][k] + shortest[k][j]){
shortest[i][j] = shortest[i][k] + shortest[k][j];
}
}
}
}
}
void findBestPlace(){
vector<pair<int, int>> combinations = getCombinations(N);
vector<pair<pair<int, int>, int>> candidates;
floydWarshall(map);
for (int i = 0; i < combinations.size(); ++i) {
int chicken1 = combinations[i].first;
int chicken2 = combinations[i].second;
int totalCost = 0;
for (int j = 1; j <= N; ++j) {
if (chicken1 == j || chicken2 == j) continue;
totalCost += 2*min(map[j][chicken1], map[j][chicken2]);
}
candidates.push_back(make_pair(combinations[i], totalCost));
}
sort(candidates.begin(), candidates.end(), comp);
cout<<candidates[0].first.first<<' '<<candidates[0].first.second<<' '<<candidates[0].second;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int M, a, b;
cin>>N>>M;
map.assign(N+1, vector<int>(N+1, INF));
for (int i = 1; i <= N; ++i) {
map[i][i] = 0;
}
for(int i=0; i<M; i++){
cin>>a>>b;
map[a][b] = 1;
map[b][a] = 1;
}
findBestPlace();
return 0;
}