백준 15686 (삼성 SW 역량평가 기출) - 치킨 배달

 이 포스팅은 삼성 GIST 모터 트랙 대비 과정에서 풀었던 기출 문제에 대한 글입니다. 모두 백준에 공개된 문제들만 있으며, SW Expert Academy에서만 다루는 문제들은 저작권 문제로 업로드 되지 않습니다.

---

1. 문제 내용

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

문제 난이도: GOLD V

2. 접근법

• 치킨 집들의 위치를 알면 집 하나 당 치킨 거리 구하기는 O(M)에 바운드 됨. 도시 전체의 치킨 거리는 O(N x M)에 구할 수 있음.
• 그런데 N과 M이 상수에 가까운 범위에 바운드 되므로 O(C)로 봐도 무방.
• 문제는 어떤 치킨 집을 남기느냐임.
• 즉, 기존의 치킨 집에서 M개의 치킨 집을 선택하는 경우의 수(조합) 문제임. 이 경우의 수 중 치킨 거리가 최소인 경우 찾기
• 경우의 수이므로 백트래킹으로 풀기

3. 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int map[50][50];
vector<pair<int, int>> houses; 
vector<pair<int, int>> chickenStores; 
vector<int> ans_stores; // 후보 치킨집들의 chickenStores 상 인덱스
bool visited[13] = {false, };
int mn = 987654321;

// O(M) 
int chickenDistForSingleHouse(int x, int y) {
    int dist = 1000;
    for(auto it : ans_stores) {
        
        int r = chickenStores[it].first;
        int c = chickenStores[it].second;
        dist = min(dist, abs(r - x) + abs(c - y));
    }
    return dist;
}

//O(N x M)
int chickenDistForCity() {
    int dist = 0;
    for(auto it : houses) {
        dist += chickenDistForSingleHouse(it.first, it.second);
    }
    return dist;
}

void solve(int store_num, int last) {
    // end case
    if(store_num == M) {
        mn = min(mn, chickenDistForCity());
        return ;
    }
    
    //avg case
    for(int i = last; i < chickenStores.size(); i++) {
        if(!visited[i]) {
            visited[i] = true;
            ans_stores.push_back(i);
            solve(store_num + 1, i + 1);
            visited[i] = false;
            ans_stores.pop_back();
        }
    }
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            int tmp; cin >> tmp;
            if(tmp == 1) {
                houses.emplace_back(i, j);
            }
            else if(tmp == 2) {
                chickenStores.emplace_back(i, j);
            }
        }
    }
    solve(0, 0);
    cout << mn << '\n';
    return 0;
}

4. 중요 포인트

• 좌표에 함몰되지 말고 가능한 풀이를 여러 개 떠올린 뒤 변수 범위로 풀이 범위를 좁히기!
• 백트래킹 사용할 때 항상 avg case의 반복문 조건을 조심할 것! 모든 범위를 커버하면서도 중복이 없도록 하기 위해 어떤 변수가 어떤 크기를 나타내는지 이중삼중으로 확인할 것.