치킨 배달 (15686번) - 백준 (BOJ)

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

백준 - 치킨 배달 (15686번)

 

난이도 : Gold 5

알고리즘&자료구조 : Exhaustive Search (완전 탐색)

 

 

import sys
input = sys.stdin.readline
from itertools import combinations as comb


if __name__ == '__main__':
    N, M = map(int, input().split())
    home = []
    chicken = []
    # ⓐ
    for r in range(N):
        for c, t in enumerate(map(int, input().split())):
            if not t:
                continue
            if t == 1:
                home.append((r, c))
            else:
                chicken.append((r, c))
    hl, cl = len(home), len(chicken)
    # ⓑ
    dist = [[sum(abs(home[h][i] - chicken[c][i]) for i in range(2)) for c in range(cl)] for h in range(hl)]
    # ⓒ
    print(min(sum(min(dist[h][i] for i in seq) for h in range(hl)) for seq in comb(range(cl), M)))

 

 

itertools의 Combinations 모듈을 활용해서, 완전 탐색으로 해결했다.

 

 

풀이 과정

 

ⓐ 집과 치킨집의 좌표를 모두 찾아서 home과 chicken에 기록한다.

 

ⓑ 각 집과 각 치킨집 사이의 모든 거리를 계산해서 dist에 저장한다.

 

ⓒ 그리고 cl 개의 치킨집 중에서 M개의 치킨집을 선택하는 모든 경우의 수 중,

최소 거리의 경우의 수를 출력한다. → Combinations : (cl)C(M)

 

 

 

---

 

다른 방법

 

Combinations 대신, Backtracking + DFS 를 활용해서 풀 수도 있다.

(코드가 상당히 길어진다...)

 

import sys
input = sys.stdin.readline


def get_coords() -> None:
    for r in range(n):
        for c in range(n):
            if village[r][c] == 1:
                home.append((r, c))
            elif village[r][c] == 2:
                chicken.append((r, c))
    return


def get_dist() -> None:
    for h in range(h_len):
        hr, hc = home[h]
        for c in range(c_len):
            cr, cc = chicken[c]
            distance[h][c] = abs(hr-cr)+abs(hc-cc)
    return


def get_min_dist(min_arr: int, depth: int, idx: int):
    if depth == m:
        global miny
        cur_sum = sum(min_arr)
        if cur_sum < miny:
            miny = cur_sum
        return
    
    for c_i in range(idx, c_len):
        replica = min_arr.copy()
        for h_i in range(h_len):
            if distance[h_i][c_i] < replica[h_i]:
                replica[h_i] = distance[h_i][c_i]
        get_min_dist(replica, depth+1, c_i+1)
    return


if __name__ == '__main__':
    n,m = map(int, input().split())
    village = [list(map(int, input().split())) for _ in range(n)]
    home = list(); chicken = list()
    get_coords()

    h_len = len(home); c_len = len(chicken)
    distance = [[0]*c_len for _ in range(h_len)]
    get_dist()

    miny = pow(10, 9)
    get_min_dist([miny]*h_len, 0, 0)
    print(miny)