백준 15686 치킨 배달

치킨 배달 풀다가 치킨 먹고 싶어서 시켜먹음..

먹고 다음날 마저 풀었다..

 

처음에 거리를 구하기 위해서 bfs로 짜다가 잘못되었음을 알고 바로 지웠다.

왜냐하면 집과 치킨 사이의 거리만 알면되기 때문이다. 최소 거리라고 적혀있어서 아무 생각없이 풀었던게 문제였다.

그냥 집과 치킨집 사이의 거리를 vector에 넣고 최소 거리만 찾으면 되는 거였다.

 

그리고 치킨집 중에서 m개를 골라야 하기 때문에 순열로 풀려고 했으나, M이 최대 13이므로 13!은 시간 초과가 뜰 것이라 생각해서 재귀함수로 풀었다.

 

치킨집 하나를 추가하고 빼는 것에 주의해야 하고, 또 다음에 선택할 번호인 idx가 vector에 있는 치킨집의 수(vector의 사이즈)를 넘을 경우 재귀가 종료된다는 것에 주의해야 한다.

idx가 m일 때 끝난다고 코딩하는 실수를 했다.

 

마지막으로 m개를 선택한 상태에서 치킨 거리를 구해야 하기 때문에 처음에 입력을 받을 때 치킨집이면 0으로 바꾼 후, 재귀 함수 안에서 치킨집을 선택할 때 다시 2로 바꿨다가 선택하지 않을 때 다시 0으로 바꾸는 방법이 주효했던 것 같다.

 

코드는 아래와 같다.(주석처리된 출력은 디버깅용)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int city[50][50];
bool visit[50][50];
int dist[50][50];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
//집 위치를 저장할 queue
vector<pair<int, int>> house;
vector<pair<int, int>> ck_house;
vector<pair<int, int>> selected_ck_house;
vector<int> ans;
int n, m;
 
int distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
 
void dfs(int idx, int cnt) {
    //고를 때 m개가 되면 치킨 거리를 구한다.
    if (cnt == m) {
        int city_min = 0;
        for (int x = 0; x < house.size(); x++) {
            int row = house[x].first;
            int col = house[x].second;
 
            //치킨 거리를 구하기 위한 vector
            vector<int> min_dis;
            //모든 치킨집 과의 거리를 구한다.
            for (int k = 0; k < selected_ck_house.size(); k++) {
                int d = distance(row, col, selected_ck_house[k].first, selected_ck_house[k].second);
                min_dis.push_back(d);
            }
            //최소 값이 치킨 거리이다.
            //계속 더해주면 도시의 치킨 거리이다.
            city_min += *min_element(min_dis.begin(), min_dis.end());
        
            //printf("ck_street: %d\n", *min_element(min_dis.begin(), min_dis.end()));
        }
        //도시의 치킨 거리 값을 ans에 넣어준다.
        ans.push_back(city_min);
        return;
    }
    //m개를 다 안골랐는데, idx가 m을 넘어서면 더이상 할 필요 없음.
    if (idx == ck_house.size())return;
    //현재 치킨집의 위치를 체크한다.
    int row = ck_house[idx].first;
    int col = ck_house[idx].second;
    //치킨 집을 city에 추가한다.
    city[row][col] = 2;
    /*출력부분(디버깅)
    printf("---------치킨집 넣고 나서--------\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", city[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------\n");
    */
    
    //고른다.
    selected_ck_house.push_back(ck_house[idx]);
    dfs(idx + 1, cnt + 1);
    
    //다시 치킨집을 0으로 바꾼다.(없앤다.)
    city[row][col] = 0;
    /*출력부분(디버깅)
    printf("---------치킨집 빼고 나서--------\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", city[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------\n");
    printf("idx: %d, cnt: %d\n", idx, cnt);
    */
 
    //안고른다.
    selected_ck_house.pop_back();
    dfs(idx + 1, cnt);
}
 
int main(int argc, char** argv) {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &city[i][j]);
            //치킨집들을 vector에 저장한다.
            if (city[i][j] == 2) {
                ck_house.push_back(make_pair(i, j));
                //선택 된 치킨집들만 city에 표시하기 위해 일단 모든 치킨 집들은 0으로 바꾼다.
                city[i][j] = 0;
            }
            //집이 몇개 있는지 센다.
            //나중에 도시의 치킨 거리를 구하기 위함이다.
            if (city[i][j] == 1) house.push_back(make_pair(i, j));
        }
    }
    /*출력부분(디버깅)*/
    //printf("\n");
    dfs(0, 0);
 
    printf("%d\n", *min_element(ans.begin(), ans.end()));
 
    return 0;
}