ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 15686.치킨배달
    알고리즘/백준 BAEK JOON 2020. 8. 11. 00:43

    이번에는 오랜만에 백준의 문제를 풀어보았다. 15686 치킨배달이라는 문제이고 재귀함수

    조합에 대한 공부를 하기 좋은 문제 같다. 난이도나 유형은 이전의 요리사와 상당히 비슷한 문제같이 느껴진다.

     

    15686번: 치킨 배달

    크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

    www.acmicpc.net

    다행이 풀어내는데 성공했고 풀어내면서 느낀점은 설계의 중요성이다. 재귀함수를 두 번 진행했기에

    설계를 잘못하면 너무 복잡해지므로 꼭 설계가 끝나기전까지는 코딩하지말자!!

     

     


     

    이 문제의 풀이 과정은 다음과 같다.

     

    1. 치킨의 좌표들 중에 M개를 선택하는 로직

    => 즉, 조합을 구현해야한다.

     

    2. 선택한 M개의 치킨좌표와 집 좌표와의 치킨거리를 구하기 

    => 이 때 최소값을 선택해야한다. 이렇게 구하게되면 최소값은 모두 집 좌표의 개수 만큼 나오게 된다.

    => 그걸 전부 더한것이 정답의 치킨거리라고 하였으니 정답의 치킨거리를 저장해놓고 최소값을 찾으면 된다.

     

     


     

    < 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
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <deque>
    #include <algorithm>
     
    #define MAX 51
     
    using namespace std;
     
    int N, M;
    int map[MAX][MAX]; // 집과 치킨 맵
    bool check[MAX];   // 조합에 사용될 배열
    bool flag;         // 재귀종료 플레그
     
    deque<pair<intint>> h; // home의 좌표
    deque<pair<intint>> c; // chicken 좌표
    deque<pair<intint>> t; // chicken 좌표 중 선택한 M개의 좌표 조합
     
    int tmp, sum, ans; // 치킨거리 저장변수, 치킨거리들의 합 변수, 정답 변수
     
    int length(int a, int b){ // 치킨거리를 구하는 함수
        int x = abs(h[a].first - t[b].first);
        int y = abs(h[a].second - t[b].second);
        return x + y;
    }
     
    // 치킨좌표의 총 개수 중 M개의 조합을 이용하여 집과 치킨집의 치킨거리를 구하는 함수
    void search(int idx1, int idx2){ // idx1 = home의 idx, idx2 = chicken 좌표 중 선택한 M의 idx  
        if (flag) // 재귀 종료 플래그가 참이면
            return// 계속 리턴
     
        if (idx1 == h.size()){     // idx1의 값이 home의 좌표갯수만큼 되면 탐색을 다했다는 의미이므로
            ans = min(ans, sum);   // 최소값을 저장함
            sum = 0;               // 합산값 초기화
            flag = true;           // 재귀 종료 플래그 활성화
            return;      
        }
     
        if (idx2 == t.size()){     // chicken 좌표 중 선택한 M개의 갯수만큼 idx2가 진행되었다면
            sum += tmp;            // 해당 home에서의 치킨거리를 더해주고
            tmp = 987654321;       // 임시 비교 변수 초기화
            return;
        }
     
        tmp = min(tmp, length(idx1, idx2)); // 치킨거리를 구하여 tmp 변수에 저장
     
        search(idx1, idx2 + 1); // 다음 재귀함수 진행 => 다음 치킨 idx로 치킨거리 탐색
        search(idx1 + 10);    // 치킨 idx를 끝까지 탐색했다면 다음 home 좌표로 다시 치킨좌표idx를 0부터 진행
     
    }
     
    // 치킨좌표의 총 개수와 M개의 조합을 만들어 내는 함수
    void choice(int start, int cnt){
     
        if (cnt == M){ // 선택한 개수가 M가 되었다면
            for (int i = 0; i < c.size(); i++)
                if (check[i])
                    t.push_back(make_pair(c[i].first, c[i].second)); // 선택된 좌표 따로 저장
     
            search(00); // 선택된 좌표들과 집과의 치킨거리 구함
            t.clear();    // 다 구했으면 선택한 좌표 초기화
            flag = false// 탐색종료 플래그 비활성
            return;
        }
     
        for (int i = start; i < c.size(); i++){ // 치킨 idx로 조합 진행 => 시작점을 잘 지정해준다.
            if (!check[i]){      // 선택안했다면
                check[i] = true// 선택
                choice(i, cnt + 1); // 다음 선택 진행
                check[i] = false;// 다음 조합을 위해 false
            }
        }
     
    }
     
    int main() {
        //freopen("15686.txt", "r", stdin);
        cin >> N >> M;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j];
                if (map[i][j] == 1
                    h.push_back(make_pair(i, j)); // 집좌표 따로저장
                else if (map[i][j] == 2)
                    c.push_back(make_pair(i, j)); // 치킨집 좌표 따로 저장
            }
        }
        ans = tmp = 987654321// 정답과 치킨거리 변수 초기화
        sum = 0;               // 치킨거리의 합 변수 초기화
        choice(0,0);           // 치킨좌표 조합 함수 진행
        cout << ans << endl;  
        return 0;
    }
    cs

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1932.정수 삼각형  (0) 2020.08.19
    1074.Z  (0) 2020.08.15
    15686.치킨배달  (0) 2020.08.11
    14503.로봇청소기  (0) 2020.06.01
    16236.아기상어  (0) 2020.05.31
    14890.경사로  (0) 2020.05.28

    댓글 0

Designed by Tistory.