15686 백준

처음 보자마자 든 생각은 bfs를 통한 최소거리 문제인가? 라고 생각했는데
단순히 "치킨집과의 거리" 가 아닌 m개가 남을 때 최소가 되는 치킨집과의 거리를 구해야하는 문제였다.
즉 거리 뿐만 아니라 어떤 치킨집을 남길지도 선택해야 하는가? 가 문제인데
문제의 input을 확인해보자.
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
여기서 치킨집의 갯수는 13보단 작고 M보단 크거나 같다
집의 개수는 2N개를 넘지 않는다
그렇다면 치킨집 중 M개를 선택하고 그것에 따른 최소거리들을 비교하는 문제를 확인해보자.

이 문제를 대충 나누면 두가지로 볼 수 있을 것 같다.

1. 치킨집을 M개로 나누는 파트
걍 dfs이용하면 나눌 수 있을 듯
2. 나눠진 치킨집에서 최소거리를 구하는 파트
집 vs 치킨집 사이의 x,y축 차이를 모두 구한다음에 선택하면 될듯 (아마 한번 비교 시 복잡도는 O(NM)일텐데 input 조건이 널널해서 문제없을 것 같다.)

구현 과정에서

남은 치킨집의 갯수 + 현재까지 온 갯수 >= 남겨야 하는 갯수

일때만 하게 한다던가

m개 남기고 거리 계산할 때 값이 output보다 커지면 거기서 그만하는

이런 것을 넣긴 했는데 문제 input상으로는 그렇게 의미가 없을 것 같다.

만약 코테라면 조건 확인하고 그냥 하는게 더 나을지도?

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;

int input_m[52][52] = {0};
int output = MY_INT_MAX;
int n,m;
vector<pair<int,int>> chicken_v;
vector<pair<int,int>> house_v;
int path[14] = {0};

int dfs(int now_idx, int now_num)
{
    if(now_num > 0)
        path[now_num] = now_idx;

    if(now_num == m)
    {
        int tmp_val = 0;
        for(int i = 0; i < house_v.size(); i++)
        {
            int tmp_min = MY_INT_MAX;
            for(int j=1; j<=m; j++)
                tmp_min = min(tmp_min, (abs(house_v[i].first - chicken_v[path[j]].first) + abs(house_v[i].second - chicken_v[path[j]].second)));
            tmp_val += tmp_min;
            if(tmp_val > output)
                return 0;
        }
        output = min(output, tmp_val);
    }

    for(int i=now_idx+1; i<chicken_v.size(); i++)
    {
        if(chicken_v.size() - i + now_num >= m)
        {
            dfs(i, now_num+1);
        }
    }

    if(now_num > 0)
        path[now_num] = 0;
    return 0;
}


void solution()
{
    // code
    cin >> n >> m;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            cin >> input_m[i][j];
            if(input_m[i][j] == 1)
                house_v.push_back(make_pair(i,j));
            else if(input_m[i][j] == 2)
                chicken_v.push_back(make_pair(i,j));
        }
    dfs(-1,0);
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    cout << output;
    return 0;
}

 

 

다른 분들의 코드를 확인하니 치킨집을 선택하는 과정이 나와는 조금 달랐다.

첫번째가 내 코드인데 나같은 경우에는 for문을 통해서 모든 경우의 수를 확인했는데

다른 분들은 두번째와 같이 코딩을 하더라.

문제의 모든 조건을 무시하고 코드적으로만 보았을때

내 코드는 대충 생각해 봤을 때 f(12) = f(11) + f(10)... + f(1)일것인데 1, 2, 4, 8, 16... 이렇게 증가할 것이다 n을 n-1로 나타내는 과정에서 대충 생각하면 2^n일것.

두번째 코드의 경우 다음 노드는 반드시 방문하되 case를 남길지, 남기지 않을지로 나눠서 dfs하는 방식이었다.  물론 이 방식의 복잡도 또한 2^n이겠지만 좀더 직관적이라는 느낌을 받았다.

 

    for(int i=now_idx+1; i<chicken_v.size(); i++)
    {
        if(chicken_v.size() - i + now_num >= m)
        {
            dfs(i, now_num+1);
        }
    }

    dp[count+1] = now_idx+1;
	dfs(now_idx+1, count+1);
    dp[count+1] = 0;
	dfs(now_idx+1, count);