[백준] 15686번 치킨 배달

📌삼성 SW 역량테스트 기출

💡문제접근

• 백트래킹과 조합론 두 방법을 이용해서 풀 수 있을 것 같다는 생각은 했지만 아직 백트래킹은 익숙하지 않아서 그런지 제대로 접근을 못하겠어서 결국 조합론을 이용해 해결했다. 폐업시키지않고 남겨둬야하는 치킨집들을 고르는 경우의 수를 combinations을 이용해서 구한 다음 집들과 치킨집과의 거리의 합을 구해 도시의 치킨 거리가 가장 작은 값이 나올 때 더해줬다.
• 백트래킹으로 접근하는 방법도 고민했는데 너무 힘들었다. 마지막에 너무 힘들어서 질문게시판에 있는 내용을 뒤져가면서 도움을 받아서 겨우 해결할 수 있었다.

💡코드(메모리 :31256KB, 시간 : 628ms)

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

N, M = map(int, input().strip().split())
chicken = []
for _ in range(N):
    chicken.append(list(map(int, input().strip().split())))

arr_chicken = []
arr_house = []
for i in range(N):
    for j in range(N):
        if chicken[i][j] == 2:
            arr_chicken.append((i, j))
        elif chicken[i][j] == 1:
            arr_house.append((i, j))

ans = 1e9
for ch in combinations(arr_chicken, M):
    tmp = 0
    for hx, hy in arr_house:
        res = 1e9
        for cx, cy in ch:
            res = min(res, abs(hx - cx) + abs(hy - cy))
        tmp += res
    ans = min(ans, tmp)
print(ans)

📌백트래킹 풀이 방법(메모리 : 31256KB, 시간 : 368ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
Map = [list(map(int, input().strip().split())) for _ in range(N)]

chicken = []          # 치킨집 리스트
house = []              # 집 리스트
choosen_chicken = []    # 선택된 치킨집 리스트
for i in range(N):
    for j in range(N):
        if Map[i][j] == 2:
            chicken.append((i, j))
        elif Map[i][j] == 1:
            house.append((i, j))

answer = 10000000
def recursive(level, idx):
    global answer
    if level == M:
        chicken_distance = 0
        for h in house:
            dist = 10000000
            for ch in choosen_chicken:
                tmp = abs(h[0] - ch[0]) + abs(h[1] - ch[1])
                dist = min(dist, tmp)
            chicken_distance += dist
        answer = min(answer, chicken_distance)
        return answer
    for i in range(idx, len(chicken)):
        if chicken[i] in choosen_chicken:
            continue
        choosen_chicken.append(chicken[i])
        recursive(level+1, i+1)
        choosen_chicken.pop()

recursive(0, 0)
print(answer)

💡소요시간 : 3h