[Inflearn] 피자 배달 거리(삼성 SW역량평가 기출 : DFS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 0은 빈칸, 1은 집, 2는 피자집

    - 행과 열은 1번부터 N번까지

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

좌표를 그려서 구하려고하니 해결책이 나오질 않았다..

결국 강사님의 힌트를 보았다..ㅠㅠ

그래도 차근차근 문제를 많이 풀어보면서

DFS랑 친해져야지..

입력이 아래와 같을 때,

4 4 

0 1 2 0 

1 0 2 1 

0 2 1 2 

2 0 1 2

좌표를 그려서 해결방법을 찾으려고하면 너무 복잡하다.

그래서 1이 입력되었을 떄는 집의 좌표를 저장하는 벡터에 좌표를 저장하고

2가 입력되었을 때는 피자집의 좌표를 저장하는 벡터에 좌표를 저장한다.

hous[]

(1,2) (2,1) (2,4) (3,3) (4,3)

pizza[]

(1,3) (2,3) (3,2) (3,4) (4,1) (4,4)

여섯개의 피자집에서 4개를 뽑아야 하므로,

여기서 조합이 사용된다.

ch[] 배열에 선택된 피자집의 조합을 저장하고,

4개의 피자집이 모두 선택되었다면

각 집으로부터 가장 가까운 피자집까지의 거리의 합을 구해야 한다.

이 값이 최솟값인 4가지 피자집 조합을 찾는 것이다...

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; #define x first #define y second #define MAX 2147000000 #define MIN -2147000000   int n, m, sum = 0, ch[13]; int rst = MAX; vector<pair<int, int> > house, pizza;   void DFS(int s, int L) {     int i, j, htp, htpMin, htpTotalMin = 0;       if (L == m)     {         for (i = 0; i < house.size(); i++)         {             htpMin = MAX;               for (j = 0; j < m; j++)             {                 htp = abs(house[i].x - pizza[ch[j]].x) + abs(house[i].y - pizza[ch[j]].y);                   if (htpMin > htp)                     htpMin = htp;             }               htpTotalMin += htpMin;         }           if (rst > htpTotalMin)             rst = htpTotalMin;     }     else     {         for (i = s; i < pizza.size(); i++)         {             ch[L] = i;             DFS(i + 1,  L + 1);         }     } }   int main(void) {     freopen("input.txt", "rt", stdin);       int i, j, a;        scanf("%d %d", &n, &m);     for (i = 1; i <= n; i++)     {         for (j = 1; j <= n; j++)         {             scanf("%d", &a);               if (a == 1)                 house.push_back({ i, j });             else if (a == 2)                 pizza.push_back({ i, j });         }     }       DFS(0, 0);       printf("%d\n", rst);       return 0; } Colored by Color Scripter

cs

위에 solve대로 구현해보았는데,

자잘한 실수가 많아서 계속 디버깅해보면서 고쳐나갔다ㅠㅠ

처음에 짤 때, 차근차근 생각하면서 푸는게 중요할 것 같다.

디버깅하면서 잘못된 부분을 찾아내는게 시간이 꽤나 소요된다...

재귀함수는 조합구하기 문제와 동일하다.

(2) 변수명이랑 코드를 좀 깔끔하게 정리해보았다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define MAX 2147000000
#define MIN -2147000000
 
int n, m, sum = 0, dist, ch[13];
int rst = MAX;
vector<pair<int, int> > house, pizza;
 
void DFS(int s, int L)
{
    int i, j, tmp, sum = 0;
 
    if (L == m)
    {
        for (i = 0; i < house.size(); i++)
        {
            dist = MAX;
 
            for (j = 0; j < m; j++)
            {
                tmp = abs(house[i].x - pizza[ch[j]].x) + abs(house[i].y - pizza[ch[j]].y);
 
                if (dist > tmp) dist = tmp;
            }
 
            sum += dist;
        }
 
        if (rst > sum) rst = sum;
    }
    else
    {
        for (i = s; i < pizza.size(); i++)
        {
            ch[L] = i;
            DFS(i + 1,  L + 1);
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int i, j, a; 
 
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &a);
 
            if (a == 1)
                house.push_back({ i, j });
            else if (a == 2)
                pizza.push_back({ i, j });
        }
    }
 
    DFS(0, 0);
 
    printf("%d\n", rst);
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int> > pz;
vector<pair<int, int> > hs;
int ch[20], m, res = 2147000000, dis, sum = 0;
 
void DFS(int L, int s) {
    if (L == m) {
        sum = 0;
        for (int i = 0; i < hs.size(); i++) {
            int x1 = hs[i].first;
            int y1 = hs[i].second;
            dis = 2147000000;
            for (int j = 0; j < m; j++) {
                int x2 = pz[ch[j]].first;
                int y2 = pz[ch[j]].second;
                dis = min(dis, abs(x1 - x2) + abs(y1 - y2));
            }
            sum = sum + dis;
        }
        if (sum < res) res = sum;
    }
    else {
        for (int i = s; i < pz.size(); i++)
        {
            ch[L] = i;
            DFS(L + 1, i + 1);
        }
    }
}
 
int main() {
    int n, i, j, a;
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &a);
            if (a == 1) hs.push_back(make_pair(i, j));
            else if (a == 2) pz.push_back(make_pair(i, j));
        }
    }
    DFS(0, 0);
    printf("%d\n", res);
    return 0;
}

line 9~32) DFS() 함수는 선택된 피자집의 개수와 이전에 선택된 피자집 idx를 매개변수로 받는다.

line 10~24) 모든 피자집이 선택되었을 경우

line 11) 선택된 피자집과 각 집의 최소 거리합을 구해야하므로 초기화

line 12~22) 모든 집과 선택된 피자집과의 거리를 구해야하므로 집의 개수만큼 반복

line 13~14) 해당 집의 좌표를 저장

line 15) 해당 집과 가장 가까운 피자집과의 거리를 구해야하므로 dist를 초기화

line 16~20) 뽑을 피자집의 개수만큼 반복

line 17~18) 선택된 피자집의 좌표를 저장

line 19) 해당 집과 해당 피자집과의 거리를 저장, 

     가장 가까운 피자집과의 거리를 구하기 위해 min() 사용

line 21) 선택된 피자집들과 각 집들과의 최소거리를 sum에 누적

line 23) 최소 거리를 저장

line 25~31) 모든 피자집이 선택되지 않았을 경우

line 26~30) 조합구하기와 동일하다. 선택할 수 있는 피자집의 조합을 구한다.

line 28) 선택한 피자집의 idx를 ch[]에 저장

line 29) 선택된 피자집 개수 + 1, 선택된 피자집의 idx + 1 을 DFS() 함수에 인자로 넘겨준다.

재귀함수 호출부분만 잘 구현해주면, 종료지점은 어렵지 않게 구현해낼 수 있을 것이다.

이번 문제도 사실 좀 헤매느라.. 아직도 한참 부족한 것 같다.

퐈이또하자..!

#. Result

  - Input --------------------------------------------------------

4 4 

0 1 2 0 

1 0 2 1 

0 2 1 2 

2 0 1 2

------------------------------------------------------------------

  - Output --------------------------------------------------------

6

------------------------------------------------------------------