백준 15686번
오늘 풀어본 문제는 백준의 15686번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
크기가 $N \times N$ 인 도시가 있다. 도시는 $1 \times 1$ 크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 $(r, c)$ 와 같은 형태로 나타내고, $r$ 행 $c$ 열 또는 위에서부터 $r$ 번째 칸, 왼쪽에서부터 $c$ 번째 칸을 의미한다. $r$ 과 $c$ 는 $1$ 부터 시작한다.
이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 “치킨 거리“라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 $(r_1, c_1)$ 과 $(r_2, c_2)$ 사이의 거리는 $|r_1-r_2| + |c_1-c_2|$ 로 구한다.
예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
$0$ 은 빈 칸, $1$ 은 집, $2$ 는 치킨집이다.
$(2, 1)$ 에 있는 집과 $(1, 2)$ 에 있는 치킨집과의 거리는 $|2-1| + |1-2| = 2$, $(5, 5)$ 에 있는 치킨집과의 거리는 $|2-5| + |1-5| = 7$ 이다. 따라서, $(2, 1)$ 에 있는 집의 치킨 거리는 $2$ 이다.
$(5, 4)$ 에 있는 집과 $(1, 2)$ 에 있는 치킨집과의 거리는 $|5-1| + |4-2| = 6$, $(5, 5)$ 에 있는 치킨집과의 거리는 $|5-5| + |4-5| = 1$ 이다. 따라서, $(5, 4)$ 에 있는 집의 치킨 거리는 $1$ 이다.
이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 $M$ 개라는 사실을 알아내었다.
도시에 있는 치킨집 중에서 최대 $M$ 개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 $N$ $(2 \le N \le 50)$ 과 $M$ $(1 \le M \le 13)$ 이 주어진다.
둘째 줄부터 $N$ 개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 $0, 1, 2$ 로 이루어져 있고, $0$ 은 빈 칸, $1$ 은 집, $2$ 는 치킨집을 의미한다. 집의 개수는 $2N$ 개를 넘지 않으며, 적어도 $1$ 개는 존재한다. 치킨집의 개수는 $M$ 보다 크거나 같고, $13$ 보다 작거나 같다.
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 $M$ 개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
풀이과정
1번째 시도
처음에 문제를 보고 생각한 것은 BFS 를 여러 번 반복하여 치킨 거리들을 계산하는 것이었다. 치킨 집을 선택하는 방식은 $1$ 에서 $2^\text{(치킨 집 수)} - 1$ 까지의 정수들을 순회하며 각각의 비트로 해당 치킨집을 선택할지 말지를 결정하게 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N, M;
int graph[50][50] = {0,};
vector<pair<int, int>> chickens;
int getDigits(int k);
int selectChickens(int k);
int getTotalDistance(int (*modifiedGraph)[50]);
int getOneDistance(int (*modifiedGraph)[50], pair<int, int> house);
bool isInRange(pair<int, int> pos);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
int info;
cin >> info;
if (info == 2) {
chickens.emplace_back(i, j);
info = 0;
}
graph[i][j] = info;
}
}
int minimum = INT_MAX;
for (int k=1; k < (1 << chickens.size()); k++) {
if (getDigits(k) > M) {
continue;
}
int temp = selectChickens(k);
minimum = min(minimum, temp);
}
cout << minimum;
return 0;
}
int getDigits(int k) {
int result = 0;
while (k > 0) {
result += (k % 2);
k >>= 1;
}
return result;
}
int selectChickens(int k) {
int modifiedGraph[50][50] = {0,};
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
modifiedGraph[i][j] = graph[i][j];
}
}
int bit = 0;
while (k > 0) {
if (k % 2 == 1) {
modifiedGraph[chickens[bit].first][chickens[bit].second] = 2;
}
bit++;
k >>= 1;
}
return getTotalDistance(modifiedGraph);
}
int getTotalDistance(int (*modifiedGraph)[50]) {
int total = 0;
vector<pair<int, int>> houses;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (modifiedGraph[i][j] == 1) {
houses.emplace_back(i, j);
}
}
}
for (auto& house : houses) {
total += getOneDistance(modifiedGraph, house);
}
return total;
}
int getOneDistance(int (*modifiedGraph)[50], pair<int, int> house) {
int shortest = INT_MAX;
queue<pair<pair<int, int>, int>> q;
bool visited[50][50] = {false,};
q.emplace(house, 0);
while (!q.empty()) {
pair<pair<int, int>, int> curr = q.front();
q.pop();
if (!visited[curr.first.first][curr.first.second]) {
visited[curr.first.first][curr.first.second] = true;
for (int i=0; i<4; i++) {
pair<int, int> next = make_pair(curr.first.first + dx[i], curr.first.second + dy[i]);
if (isInRange(next) && !visited[next.first][next.second]) {
if (modifiedGraph[next.first][next.second] == 2) {
shortest = min(shortest, curr.second + 1);
}
else {
q.emplace(next, curr.second + 1);
}
}
}
}
}
return shortest;
}
bool isInRange(pair<int, int> pos) {
if (pos.first < 0 || pos.first > N-1) {
return false;
}
else if (pos.second < 0 || pos.second > N-1) {
return false;
}
else {
return true;
}
}
실행 결과 ‘시간 초과’가 발생하였다.
2번째 시도
시간 초과가 발생한 원인으로 생각해낸 것은, 치킨 거리를 구하는데에 있어서 BFS를 사용할 필요가 없다는 것이었다. 치킨 거리의 정의 자체가 그냥 택시 거리와 동일하기 때문에 간단한 연산으로 알아낼 수 있는 것이었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int N, M;
int graph[50][50] = {0,};
vector<pair<int, int>> chickens;
int getDigits(int k);
int selectChickens(int k);
int getTotalDistance(int (*modifiedGraph)[50]);
int getOneDistance(int (*modifiedGraph)[50], pair<int, int> house);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
int info;
cin >> info;
if (info == 2) {
chickens.emplace_back(i, j);
info = 0;
}
graph[i][j] = info;
}
}
int minimum = INT_MAX;
for (int k=1; k < (1 << chickens.size()); k++) {
if (getDigits(k) > M) {
continue;
}
int temp = selectChickens(k);
minimum = min(minimum, temp);
}
cout << minimum;
return 0;
}
int getDigits(int k) {
int result = 0;
while (k > 0) {
result += (k % 2);
k >>= 1;
}
return result;
}
int selectChickens(int k) {
int modifiedGraph[50][50] = {0,};
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
modifiedGraph[i][j] = graph[i][j];
}
}
int bit = 0;
while (k > 0) {
if (k % 2 == 1) {
modifiedGraph[chickens[bit].first][chickens[bit].second] = 2;
}
bit++;
k >>= 1;
}
return getTotalDistance(modifiedGraph);
}
int getTotalDistance(int (*modifiedGraph)[50]) {
int total = 0;
vector<pair<int, int>> houses;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (modifiedGraph[i][j] == 1) {
houses.emplace_back(i, j);
}
}
}
for (auto& house : houses) {
total += getOneDistance(modifiedGraph, house);
}
return total;
}
int getOneDistance(int (*modifiedGraph)[50], pair<int, int> house) {
vector<pair<int, int>> leftChicken;
int shortest = INT_MAX;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (modifiedGraph[i][j] == 2) {
leftChicken.emplace_back(i, j);
}
}
}
for (auto& chicken : leftChicken) {
shortest = min(shortest, abs(house.first - chicken.first) + abs(house.second - chicken.second));
}
return shortest;
}
실행 결과 ‘시간 초과’가 발생하였다.
3번째 시도
여전히 시간 초과가 나는 이유를 고민해보았고, 이는 매번 modifiedGraph 변수를 새로 만들어 인자로 전달해주기 때문이라는 결론에 도달했다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int N, M;
int graph[50][50] = {0,};
vector<pair<int, int>> chickens;
int getDigits(int k);
int selectChickens(int k);
int getTotalDistance(void);
int getOneDistance(pair<int, int> house);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
int info;
cin >> info;
if (info == 2) {
chickens.emplace_back(i, j);
info = 0;
}
graph[i][j] = info;
}
}
int minimum = INT_MAX;
for (int k=1; k < (1 << chickens.size()); k++) {
if (getDigits(k) > M) {
continue;
}
int temp = selectChickens(k);
minimum = min(minimum, temp);
}
cout << minimum;
return 0;
}
int getDigits(int k) {
int result = 0;
while (k > 0) {
result += (k % 2);
k >>= 1;
}
return result;
}
int selectChickens(int k) {
int result;
int bit = 0;
int temp = k;
while (temp > 0) {
if (temp % 2 == 1) {
graph[chickens[bit].first][chickens[bit].second] = 2;
}
bit++;
temp >>= 1;
}
result = getTotalDistance();
bit = 0;
temp = k;
while (temp > 0) {
if (temp % 2 == 1) {
graph[chickens[bit].first][chickens[bit].second] = 0;
}
bit++;
temp >>= 1;
}
return result;
}
int getTotalDistance(void) {
int total = 0;
vector<pair<int, int>> houses;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (graph[i][j] == 1) {
houses.emplace_back(i, j);
}
}
}
for (auto& house : houses) {
total += getOneDistance(house);
}
return total;
}
int getOneDistance(pair<int, int> house) {
vector<pair<int, int>> leftChicken;
int shortest = INT_MAX;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (graph[i][j] == 2) {
leftChicken.emplace_back(i, j);
}
}
}
for (auto& chicken : leftChicken) {
shortest = min(shortest, abs(house.first - chicken.first) + abs(house.second - chicken.second));
}
return shortest;
}
실행 결과 ‘시간 초과’가 발생하였다.
4번째 시도
계속된 시간 초과의 근본적인 원인으로 떠올린 것은, 애초에 graph 도 필요가 없다는 것이었다. 우리는 치킨 거리를 계산하기 위해서 집들과 치킨집들의 위치만 알면 되었던 것이다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<pair<int, int>> houses;
vector<pair<int, int>> chickens;
int getDigits(int k);
int getTotalDistance(int k);
int getOneDistance(int k, pair<int, int> house);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
int info;
cin >> info;
if (info == 1) {
houses.emplace_back(i, j);
}
else if (info == 2) {
chickens.emplace_back(i, j);
}
}
}
int minimum = INT_MAX;
for (int k=1; k < (1 << chickens.size()); k++) {
if (getDigits(k) > M) {
continue;
}
int temp = getTotalDistance(k);
minimum = min(minimum, temp);
}
cout << minimum;
return 0;
}
int getDigits(int k) {
int result = 0;
while (k > 0) {
result += (k % 2);
k >>= 1;
}
return result;
}
int getTotalDistance(int k) {
int total = 0;
for (auto& house : houses) {
total += getOneDistance(k, house);
}
return total;
}
int getOneDistance(int k, pair<int, int> house) {
int bit = 0;
int temp = k;
int shortest = INT_MAX;
while (temp > 0) {
if (temp % 2 == 1) {
shortest = min(shortest, abs(house.first - chickens[bit].first) + abs(house.second - chickens[bit].second));
}
bit++;
temp >>= 1;
}
return shortest;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
매번 그리드 형태로 입력이 주어지는 문제를 BFS로 푸는데 익숙하다보니, 이 문제도 BFS 문제라고 착각했던게 기나긴 삽질의 시작이었던 것 같다. 마지막 CLASS 4 문제는 나름 큰 관문이었던 것 같다.
어쨌든 나는 CLASS 4의 마지막 문제를 해결해냈고, 결국 CLASS 4 MASTER 를 달성하게 되었다!
(수정: 2024-06-09) 라고 생각했는데 아니었다! 솔브드 업데이트로 인해 아직 더 풀 문제들이 몇 개 남아있다. 아래의 감상은 굳이 지우진 않고 남겨두겠다.
내일부터는 CLASS 5 문제들을 위주로 풀어보게 될 것이다. 이번엔 어떤 고난이 기다리고 있을지 조금 걱정되면서도 기대가 된다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/15686