[백준/C++] 15686 - 치킨 배달

풀이 시간: 1h23m18s29 + 1h20m44s32 + 42m34s25

시간 복잡도: O(NMH) // H: 집의 개수

공간 복잡도: O(N^2)

참고 자료: https://yabmoons.tistory.com/50

문제

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

문제 풀이

초기 고민

치킨집을 최대 M를 꼭 골라야한다는 점이 골치 아프다.

그냥 각 집별로 가장 가까운 거리의 치킨집을 하나씩 고르기만 하면 되는 문제라면 그냥 bfs로 간단하게 풀 수 있다.

하지만 이 문제는 그렇지 않다.

만약 각 집마다 가장 가까운 거리의 치킨집을 고른다고 해도 N == M이 아닌 경우, 다음과 같은 문제가 발생한다.

 

N > M인 경우, N에서 가장 먼 거리부터 하나씩 거리를 없애주어 N == M이 되도록 해야 한다.

N < M인 경우, N개의 치킨집을 고르고 추가로 집을 더 돌면서 M개까지 거리를 추가해야한다.

 

일단 이렇게 된다면 그냥 N개의 집에서 모든 치킨집을 탐색하는수밖에 없다.

이때 해야할 것은 각 집마다 모든 치킨집의 거리를 저장하는 것이다.

문제의 출력은 도시의 치킨거리, 즉, 모든 집에서 치킨 거리의 합의 최솟값을 출력하는 것이기 때문에, 그냥 집과 관계없이 하나의 배열로 치킨 거리들을 하나하나 저장해주면 된다.

 

단 이때, 거리가 짧은 순서대로 저장을 해준다. 왜냐하면 치킨 거리의 최솟값을 찾는 것인데, 모든 집이 모든 치킨 거리를 계산하여 저장한 배열에서 치킨집을 M개까지만 남겨두고 나머지는 다 없애야 하기 때문이다.

이때 없애야 하는 치킨집은 치킨 거리가 가장 큰 순서대로 하나씩 없애주어야 하기 때문에 정렬이 필요하다.

 

일단 내가 생각한 방식대로 구현해보고자 하였다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> dist;
vector<pair<int, int>> home;
int N, M;
int arr[51][51] = { 0, };
int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

void bfs() {
    for (int i = 0; i < home.size(); ++i) {
        int chicken = 0; // 치킨집 개수
        vector<vector<int>> visited(N, vector<int>(N, false));
        queue<pair<int, int>> q;
        q.push({home[i].first, home[i].second});
        visited[home[i].first][home[i].second] = true;
        while (!q.empty()) {
            int cR = q.front().first;
            int cC = q.front().second;
            q.pop();
            for (int j = 0; j < 4; ++j) {
                int nR = cR + dir[j][0];
                int nC = cC + dir[j][1];
                if (nR < 0 || nR >= N || nC < 0 || nC >= N || visited[nR][nC]) continue;
                if (arr[nR][nC] == 2) dist.push_back(abs(home[i].first - nR) + abs(home[i].second - nC));
                q.push({nR, nC});
                visited[nR][nC] = true;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == 1)
                home.push_back({i, j});
        }
    bfs();
    int ans = 0;
    sort(dist.begin(), dist.end());
    for (int i = 0; i < dist.size(); ++i) { // test code
        cout << dist[i] << ", ";
    }
    for (int i = 0; i < M; ++i) ans += dist[i];
    cout << "\n" << ans;
    return 0;
}

그런데 결과가 자꾸 다음과 같이 나왔다.

// 입력
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
// 출력
1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 5, 6
3

보아하니, 집에서부터 모든 치킨집의 거리를 재는 것이 아닌, 치킨집에서 각 집의 거리들을 탐색해야하는 것 같았다.

 

1. 치킨집에서 모든 집까지의 거리를 전부 탐색하여 거리의 합을 구함

2. 위에서 구한 거리의 합(dist)이 가장 작은 치킨집들부터 차례대로 정렬 후, M개의 치킨집을 두고 나머지는 제거

3. 이제 그 남은 치킨집들을 기준으로 두고, 각 집에서부터 탐색을하면서 가장 가까운 치킨집을 하나 선택

4. 그렇게 해서 모든 치킨 거리의 합을 구함

 

다시 코드를 수정해보았다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
vector<pair<int, int>> dist;
vector<pair<int, int>> home, chick;
int N, M, ans = 0;
int arr[51][51] = { 0, };
int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

void findChick() {
    for (int i = 0; i < chick.size(); ++i) {
        queue<pair<int, int>> q;
        bool visited[51][51] = { false, };
        q.push({chick[i].first, chick[i].second});
        visited[q.front().first][q.front().second] = true;
        while (!q.empty()) {
            int cR = q.front().first;
            int cC = q.front().second;
            q.pop();
            for (int j = 0; j < 4; ++j) {
                int nR = cR + dir[j][0];
                int nC = cC + dir[j][1];
                if (nR < 0 || nR >= N || nC < 0 || nC >= N || visited[nR][nC]) continue;
                if (arr[nR][nC] == 1) {
                    dist[i].first = i; // 각 치킨집의 index
                    dist[i].second += abs(chick[i].first  - nR) + abs(chick[i].second - nC);
                }
                visited[nR][nC] = true;
                q.push({nR, nC});
            }
        }
    }
}

void findHome() {
    for (int i = 0; i < home.size(); ++i) {
        queue<pair<int, int>> q;
        bool visited[51][51] = { false, };
        q.push({home[i].first, home[i].second});
        visited[q.front().first][q.front().second] = true;
        while (!q.empty()) {
            int cR = q.front().first;
            int cC = q.front().second;
            q.pop();
            if (arr[cR][cC] == 2) {
                ans += abs(home[i].first  - cR) + abs(home[i].second - cC);
                break;
            }
            for (int j = 0; j < 4; ++j) {
                int nR = cR + dir[j][0];
                int nC = cC + dir[j][1];
                if (nR < 0 || nR >= N || nC < 0 || nC >= N || visited[nR][nC]) continue;
                visited[nR][nC] = true;
                q.push({nR, nC});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) home.push_back({i, j});
            else if (arr[i][j] == 2) chick.push_back({i, j});
        }
    dist = vector<pair<int, int>>(chick.size(), {0, 0});
    findChick(); // 치킨집 기준으로 모든 집까지의 거리 탐색
    sort(dist.begin(), dist.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second; // 두 번째 값(거리)을 기준으로 오름차순 정렬
    });
    // arr 배열에 M개 치킨집 외의 나머지 치킨집 삭제
    for (int i = M; i < dist.size(); ++i) {
        int x = chick[dist[i].first].first;
        int y = chick[dist[i].first].second;
        arr[x][y] = 0;
    }
    findHome(); // 집을 기준으로 가장 가까운 치킨집 탐색
    cout << ans; // 치킨 거리
    return 0;
}

테스트케이스는 다 맞는데 그냥 바로 틀렸다고 나온다..

그래서 질문게시판의 반례를 찾아보았다.

https://www.acmicpc.net/board/view/95024

위의 반례가 있었다.

내 코드는 아래의 반례에서 정중앙부분과 함께 순서대로 거리를 탐색하게 되어, 결국 답이 4가 아닌 6이 나온다.

// 입력
5 4
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2
// 정렬된 dist 출력: (치킨 인덱스, 해당치킨에서 모든 집까지의 총합)
2, 12
0, 16
1, 16
3, 16
4, 16
// 결과
6

질문 게시판을 더 찾아보니 나랑 동일한 로직으로 푼 사람이 있었다...

https://www.acmicpc.net/board/view/57110

아무래도 이렇게 푸는 방식이 아예 틀린 것 같다.. 그래서 그냥 정답 코드 참고해보기로 했다.

 

내가 참고한 블로그는 다음과 같다.

https://yabmoons.tistory.com/50

전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
bool isSelected[13] = { false, };
int N, M, ans = 1e9, arr[50][50] = { 0, };
vector<pair<int, int>> house, chicken, temp;

int calDis() { // 총 치킨 거리 반환
    int sum = 0;
    for (int i = 0; i < house.size(); ++i) { // 집 전체 순회
        int x = house[i].first;
        int y = house[i].second;
        int d = 1e9;
        for (int j = 0; j < temp.size(); ++j) { // 각 집마다 가장 가까운 치킨집 선택
            int xx = temp[j].first;
            int yy = temp[j].second;
            int dd = abs(xx - x) + abs(yy - y);
            d = min(dd, d);
        }
        sum += d;
    }
    return sum;
}

void selectChicken(int idx, int cnt) {
    // M개의 치킨집 선택, 최소 거리로 갱신
    if (cnt == M) { ans = min(ans, calDis()); return; }
    for (int i = idx; i < chicken.size(); ++i) { // 모든 치킨 탐색 필요
        if (isSelected[i]) continue; // 이미 선택한 치킨집은 패스
        // 선택된 치킨집
        isSelected[i] = true;
        temp.push_back(chicken[i]);
        // DFS
        selectChicken(i, cnt + 1);
        // 백트래킹
        isSelected[i] = false;
        temp.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) house.push_back({i, j});
            if (arr[i][j] == 2) chicken.push_back({i, j});
        }
    }
    selectChicken(0, 0);
    cout << ans;
    return 0;
}

 

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달