[백준] 15686번 치킨 배달- 파이썬

코딩 코딩 코오딩 2022. 3. 29. 17:44

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

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

import sys
from itertools import combinations
n, m = map(int, sys.stdin.readline().split())
graph = []

for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

chick=[]
homes = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 2 :
            chick.append((i,j))
        if graph[i][j] ==1:
            homes.append((i,j))
ans = 1000000
best_chick= list(combinations(chick,m))

for i in range(len(best_chick)):
    tmp_ans = 0
    for home in homes:
        a, b=home
        tmp = 10000
        for j in range(m):
            c, d = best_chick[i][j]
            chick_len = abs(a - c) + abs(b - d)
            if tmp >= chick_len:
                tmp = chick_len
        tmp_ans += tmp

    if ans >= tmp_ans:
        ans = tmp_ans

print(ans)

브루트포스 알고리즘 알고리즘으로 풀면 된다 모든 경우 구하고 다 답 구하고 3중 for문이 마음에 조금 걸리기는 했지만 암튼 맞음!