[ 백준 15686 ] 치킨 배달 - Python

문제 보기

이 문제는 완전 탐색 문제이다.

 

치킨 집의 위치 중에서 M개를 고른 모든 경우의 수를 탐색하면 된다.

 

알고리즘 순서는 다음과 같다.

1. 치킨 집의 위치를 저장한다.

2. 치킨 집의 위치 중 M개를 고른다. (조합)

3. 치킨 거리를 계산하고 최솟값을 계속해서 업데이트한다.

  - (x1, y1)과 (x2, y2) 거리 -> abs(x2 - x1) + abs(y2 - y1)

 

코드

import itertools, sys, copy
if __name__ == "__main__":
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]

    # 치킨집 탐색
    chicken = []
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 2:
                chicken.append([i, j])
                arr[i][j] = 0  # 빈 칸으로 수정

    # 치킨집 중에 M개 고르기(조합)
    result = list(itertools.combinations(chicken, M))

    # 탐색
    min_distance = sys.maxsize
    for i in range(len(result)):
        distance = 0
        for m in range(N):
            for n in range(N):
                if arr[m][n] == 1:
                    temp = sys.maxsize
                    for j in range(M):
                        temp = min(temp, abs(m - result[i][j][0]) + abs(n - result[i][j][1]))
                    distance += temp
        min_distance = min(min_distance, distance)

    # 출력
    print(min_distance)