[BOJ] 15686. 치킨 배달

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

15686번: 치킨 배달

 

 

1. 해결 방법

완전 탐색 (백트래킹) 문제이다.
본인은 dfs말고 조합으로 접근하였다.  물론 두 가지다 하겠지만 순열, 조합 라이브러리를 사용한 경험이 적다보니 완전 탐색 알고리즘에서 다 사용해볼 예정이다.

접근 방식은 치킨집의 위치와 집의 위치를 각 리스트에 저장한다.

먼저 치킨집을 for문 돌고, 다음으로 집을 for문 돈다. 
그 전에 조합을 이용해서 M만큼의 치킨집을 리스트로 구현하고, 각 집에서 조합 리스트의 각각의 치킨집의 dist 거리를 구한다.

구한 dist를 min() 메서드로 최솟값을 구하고, city_dist에 min으로 구한 최솟값을 더한다.


백트래킹을 이용한 방법도 마찬가지로 재귀함수를 호출하면서 그 안에 종료 지점를 if문으로 설정하고, for문과 방문 여부 chk로 조합을 구현하면 된다.

 

 

2. 정답 코드

(1) combinations

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

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

# main
city = []
chicken = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            city.append((i, j))
        if maps[i][j] == 2:
            chicken.append((i, j))

result = []
new_chicken = list(combinations(chicken, M))

answer = sys.maxsize
for new_ch in new_chicken:
    city_dist = 0
    for home in city:
        min_v = sys.maxsize
        for ch in new_ch:
            min_v = min(min_v, abs(home[0] - ch[0]) + abs(home[1] - ch[1]))

        city_dist += min_v
    answer = min(answer, city_dist)

print(answer)

 

(2) 백트래킹

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

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

# dfs
def dfs(depth, num):
    global result, chk

    # 종료 지점
    if depth == M:
        dist = 0
        for home in city:
            min_v = sys.maxsize
            for chic in chicken_list:
                min_v = min(min_v, abs(home[0] - chic[0]) + abs(home[1] - chic[1]))
            dist += min_v
        result.append(dist)
        return

    # combination
    for i in range(num, len(chicken)):
        if chk[i] == False:
            chk[i] = True
            chicken_list.append(chicken[i])
            dfs(depth + 1, i + 1)
            chk[i] = False
            chicken_list.pop()

# main
result = []
city = []
chicken = []
chicken_list = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            city.append((i, j))
        if maps[i][j] == 2:
            chicken.append((i, j))

chk = [False] * (len(chicken))
dfs(0, 0)
print(min(result))

완전 탐색 공부가 부족한 것도 있겠지만, 그렇다 하더라도 시간이 오래 걸렸다..

아이디어는 쉽지만 코드로 옮기는 과정에서 굉장히 많은 실패를 했다.