삼성 SW 역량테스트 백준 치킨배달 15686

2021-04-21

1. 문제 링크

2. 문제 조건

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

3. 컴퓨팅 사고

0은 빈칸, 1은 집, 2는 치킨집을 갖는 하나의 맵이 주어진다.
간혹 이것을 BFS로 생각하여 풀이를 할 수 있는 경우가 있을 텐데, 문제를 자세히 읽어보면 상하좌우의 방향이 주어지긴하지만 결국 우리에겐 필요한 것은 집과 치킨과의 치킨거리를 구하는것입니다. 즉 DFS 브루트포스 방법을 사용할 것입니다.
집과 치킨집과의 거리의 좌표값을 기반으로 |집 X - 치킨 X| + |집 Y - 치킨 Y|의 값을 구하는것이라고 생각하면 됩니다.
집에서 치킨집중 최대 M개를 고르는 문제가 여기서 핵심 포인트입니다. 집하나에서 M개의 치킨집을 고를 수 있습니다. 즉, 브루트포스로 치킨집 M개를 선택하는 basement의 조건을 가질 수 있습니다.
치킨집을 1개를 골랐을때의 치킨거리의 최솟값, 치킨집 2개를 골랐을때의 최솟값…M개를 골랐을때의 최솟값을 구하는것입니다.
치킨집은 좌표상 고를 수도 있고 안고를수도 있는 브루트포스 호출조건을 잘생각해야합니다. 치킨집에 3개 A,B,C가 있다고 가정했을때 A / AB / AC / BC / ABC 의 경우를 고른다고 생각을 하셔야합니다. 이때, M개를 선택해야하므로 가능한 선택의 수는 AB,AC,BC가 될 것입니다.

치킨 배달 순서

좌표에서 집인경우 집의 좌표를 담을 벡터를 선언합니다.
좌표에서 치킨집인 경우 치킨집의 좌표를 담을 벡터를 선언합니다.
DFS(0,0) 을 호출합니다. 첫번째 파라미터는 현재 치킨집의 순서, 두번째 파라미터는 현재 선택된 치킨집의 개수를 뜻합니다.
치킨집은 M개까지 선택하였을때 집과 치킨거리를 계산하여 최솟값으로 업데이트 시켜줍니다. 치킨이 선택된 것을 체크해주기 위한 check배열을 선언해줍니다.
아직 M개가 선택되지 않았더라면

check[idx] = true;
dfs(idx+1, cnt+1);
check[idx] = false;
dfs(idx+1, cnt);

치킨을 선택한 경우와 치킨을 선택하지 않은 경우로 나누어주면서 DFS를 모두 수행해줍니다.
5. M개를 선택하였을때 모든 치킨거리값을 ans의 값과 갱신하여 최솟값을 구해줍니다.
주의 해야할점은 치킨거리의 거리와 모든 집의 치킨거리는 다릅니다.
6. 만약 idx값이 치킨값보다 클경우 종료시켜줍니다. 조건에 위배됩니다.

4. Java를 활용한 문제 재풀이

4.1. 컴퓨팅 사고

N*N(2<=N<=50)의 지도가 주어집니다.
치킨거리는 집과 치킨집사이의 거리를 뜻합니다.
모든집의 치킨거리의 합은 각집당 모든치킨집사이의 거리중 가장 작은 값들의 합을 뜻합니다.
지도상에 0: 빈칸, 1:집, 2: 치킨집을 뜻합니다.
예를 들면, (2,1) 집 (1,2) 치킨집이 있으면 치킨 거리 = |2-1| + |1-2| = 2를 뜻하게 됩니다. 각 도시의 치킨거리는 = 하나의 집을 기준으로 나머지 치킨집의 치킨거리를 구한 값중 가장작은값의 합들을 뜻합니다. 처음에 문제를 제대로 읽지 않아서 헷갈리는 부분이었습니다.
최대 M개의 치킨집의 개수를 고를 수 있으므로 결국, 치킨배달의 문제는 N개중 M개를 선택하는 문제인 순열과 조합을 떠올릴 수 있습니다.
문제에서 뜻하는 바로는 도시의 치킨거리가 가장작은 값을 구하는것이므로 치킨집 리스트중에서 M개를 선택하였을때의 최솟값을 구해주면됩니다.

4.2. 아이디어

입력 N이 주어지고 R, C의 길이를 뜻합니다. N(치킨집)개의 중에서 M개를 선택할지를 구하는 M을 입력받습니다.
입력으로 주어진 값이 ‘1’일 경우 집 -> house의 리스트에 담습니다.
입력으로 주어진 값이 ‘2’일 경우 집 -> chicken의 리스트에 담습니다.
DFS를 수행하여 모든 조합을 구해줍니다.
1. 종료조건: 종료조건은 N개의 치킨집중에서 M개를 선택한 조건이 됩니다. 즉, 선택된 개수(CNT) == 선택해야할 개수(M)이 종료조건이 됩니다. 치킨 거리는 집에서 가장 가까운거리를 구하는것이므로 처음에는 BFS를 떠올렸지만, 전혀 문제풀이와 상관이 없는 지도맵이였습니다. 도시의 치킨거리는 모든집의 치킨거리의 합을 나타내므로 종료조건에 걸렸을때 모든집의 치킨거리를 구해줍니다.
2. 예를 들면, 각집(x,y) , 치킨집1,2,3 이 있으면 Math.min((집 X - 치킨집 X) + (집 Y - 치킨집 Y))의 최솟값을 구하여서 하나의 sum 변수에 더해나갑니다. 이렇게 모든하우스의 경우와 모든 치킨집의 경우를 모두 찾아내게 되면 하나의 조합의 경우로 만들 수 있는 모든도시의 치킨거리의 합을 하나 구하게 됩니다. 하나의 재귀 종료조건에 걸리게 되면 이떄 하나의 모든도시의 치킨거리의 합을 구하는것과 같습니다.
3. 수행조건: 처음에는 순열로 모든값을 구해주었지만 시간초과가 나오는 불상사가 발생하였습니다. 조합을 사용하여 중복값을 제거하여 통과를 시켰습니다.
4. 예를 들면, [1,2,3,4]라는 배열에서 1,2,3의 값을 뽑았으면 [1,2,3],[2,3,1],[3,2,1]과 같이 순열은 이전의 값들도 쳐다보는게 됩니다. 따라서 조합의 경우를 구하면 [1,2,3],[2,3,1],[3,2,1]은 다 같이 하나의 조건으로 생각하기때문에 순열에 비해 시간복잡도가 줄어들게 됩니다. 따라서 ,순열의 경우를 조합으로 변경하니 시간초과를 해결할 수 있었습니다.

5. 소스 코드

package Samsung.done;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// 순열로 돌리니까 시간초과, 조합으로 돌리니까 통과
public class 치킨배달_15686번 {
    static int[][] map;
    static int answer;
    static boolean[] isCheck;
    static List<Graph> houseList;
    static List<Graph> chickenList;
    static List<Graph> selectChickenList;
    static int n,m;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][n];
        answer = Integer.MAX_VALUE;
        houseList = new ArrayList<>();
        chickenList = new ArrayList<>();
        selectChickenList = new ArrayList<>();

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    houseList.add(new Graph(i, j));
                } else if (map[i][j] == 2) {
                    chickenList.add(new Graph(i, j));
                }
            }
        }
        isCheck = new boolean[chickenList.size()];
        dfs(0,0);
        System.out.println(answer);
    }

    private static void dfs(int cnt, int idx) {

        if(cnt == m){
            // 모든 도시의 치킨집
            int totalChickenPrice = 0;
            for(int i=0; i<houseList.size(); i++) {
                int sum = Integer.MAX_VALUE;
                Graph houseGraph = houseList.get(i);
                for (int j = 0; j < selectChickenList.size(); j++) {
                    Graph chickenGraph = selectChickenList.get(j);
                    sum = Math.min(sum,Math.abs(houseGraph.x - chickenGraph.x) + Math.abs(houseGraph.y - chickenGraph.y));
                }
                totalChickenPrice += sum;
            }
            answer = Math.min(answer, totalChickenPrice);
            return;
        }

        for(int i=idx; i<chickenList.size(); i++){
            if(isCheck[i]) continue;
            isCheck[i] = true;
            selectChickenList.add(new Graph(chickenList.get(i).x, chickenList.get(i).y));
            dfs(cnt+1,i);
            selectChickenList.remove(selectChickenList.size()-1);
            isCheck[i] = false;
        }
    }

    private static class Graph {
        int x;
        int y;

        public Graph(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

//
//  치킨배달15686.cpp
//  algorithm-ps
//
//  Created by kgh on 2020/09/21.
//  Copyright © 2020 kgh. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<pair<int,int>> house;
vector<pair<int,int>> chicken;
int map[51][51];
bool check[51];
int n,m = 0;
const int MAX = 100001;
int ans = MAX;
void dfs(int idx,int cnt){
    // 치킨 사이즈를 넘게되었을 경우
    if(idx > chicken.size()){
        return;
    }
    // 치킨집 m개를 선택하였을때
    if(cnt == m){
        int chicken_street = 0;
        for(int i=0; i<house.size(); i++){
            int dist = MAX;
            for(int j=0; j<chicken.size(); j++){
                if(check[j] == true){
                    int ax = house[i].first;
                    int ay = house[i].second;
                    int bx = chicken[j].first;
                    int by = chicken[j].second;
                    
                    int distance = abs(ax-bx) + abs(ay-by);
                    dist = min(dist,distance);
                }
            }
            chicken_street += dist;
        }
        ans = min(ans, chicken_street);
        return;
    }
    // 치킨 선택
    check[idx] = true;
    dfs(idx+1, cnt+1);
    // 치킨 미선택
    check[idx] = false;
    dfs(idx+1, cnt);
}
int main(void){
    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){
                house.push_back({i,j});
            }
            if(map[i][j] == 2){
                chicken.push_back({i,j});
            }
        }
    }
    dfs(0,0);
    cout << ans << '\n';
    return 0;
}

AlgorithmSW역량테스트