15686. 치킨 배달

문제

백준 15686번 치킨 배달

---

풀이

먼저 주어진 지도에서 모든 치킨집의 위치를 chicken에 저장해두고,

chicken = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            chicken.append((i, j))

itertools의 combinations()을 사용하여 모든 경우를 구한다.
리스트 cases에 m개의 치킨집을 조합한 모든 케이스가 담겨있다.

cases = list(combinations(chicken, m))

각 케이스마다 tot(도시의 치킨 거리)를 계산하기 위해 board에 대해 탐색을 시작한다.

• board[x][y]가 집일 때
  존재하는 치킨집들 중 해당 집과 가장 가까운 거리를 구한다. -> distance
tot(도시의 치킨 거리)에 distance를 누적한다.

해당 케이스에 대한 board의 탐색이 끝나면 answer(도시의 최소 치킨 거리)를 갱신해준다.

answer = 1e9
for case in cases:
    tot = 0
    for x in range(n):
        for y in range(n):
            if board[x][y] == 1:
                distance = 1e9
                for cx, cy in case:
                    distance = min(distance, abs(cx-x) + abs(cy-y))
                tot += distance
    answer = min(answer, tot)

다음 케이스를 탐색하며 최종값을 구한다.

전체 코드

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
chicken = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            chicken.append((i, j))

answer = 1e9
cases = list(combinations(chicken, m))
for case in cases:
    tot = 0
    for x in range(n):
        for y in range(n):
            if board[x][y] == 1:
                distance = 1e9
                for cx, cy in case:
                    distance = min(distance, abs(cx-x) + abs(cy-y))
                tot += distance
    answer = min(answer, tot)
print(answer)

---