문제 푼 날짜 : 2021-09-28

문제

문제 링크 : https://www.acmicpc.net/problem/15686

접근 및 풀이

문제에 주어진 입력의 크기가 그렇게 크지 않아서 완전 탐색으로 충분히 풀 수 있다고 판단하였고, dfs로 구현하였다.
전체적인 코드는 아래의 생각대로 구현하였다.

1. 입력을 받으면서 그냥 집(1)과 치킨집(2)의 위치를 모두 저장해준다.
2. 조합을 구현하여 주어진 치킨집 위치 중에 M개를 골라준다.
   2-1. M개의 치킨집과 모든 집간의 최소 치킨거리의 합을 구해준다.
3. 2.의 조합이 다 구해질 때까지 반복하여 치킨거리의 합의 최솟값을 return한다.

코드

// 백준 15686번 : 치킨 배달
#include <iostream>
#include <vector>

using namespace std;

#define INF 987654321

int N, M, ans = INF;
int city[51][51];
vector<pair<int, int>> house, chicken;
bool visited[14] = { false, };

int calculate(pair<int, int> h, pair<int, int> c) {
    return abs(h.first - c.first) + abs(h.second - c.second);
}

void dfs(int idx, int cnt) {
    if (cnt == M) {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            pair<int, int> hpos = house[i];
            int minDiff = INF;
            for (int j = 0; j < chicken.size(); j++) {
                pair<int, int> cpos = chicken[j];
                if (visited[j]) {
                    minDiff = min(minDiff, calculate(hpos, cpos));
                }
            }
            sum += minDiff;
        }
        ans = min(ans, sum);
        return;
    }
    for (int i = idx; i < chicken.size(); i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        dfs(i, cnt + 1);
        visited[i] = false;
    }
}

int main() {
    cin >> N >> M;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> city[i][j];
            
            if (city[i][j] == 1) {
                house.push_back(make_pair(i, j));
            } else if (city[i][j] == 2) {
                chicken.push_back(make_pair(i, j));
            }
        }
    }
    dfs(0, 0);
    
    cout << ans;
    return 0;
}

결과

피드백

이런 구현 문제는 풀 때마다 재미있다.