문제 풀이/백준(BOJ)
[Python] 백준 15686번 : 치킨 배달
희조당
2023. 2. 27. 12:48
728x90
https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
💡 문제 풀이
기본적인 구현, DFS 문제이다.
✔️ 느낀 점
💻 코드
import sys
from itertools import combinations
input = sys.stdin.readline
N, M = map(int, input().split())
board = [list(map(int, input().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])
def calc(chicken):
dist = 0
for i in range(N):
for j in range(N):
if board[i][j] == 1:
min_ = sys.maxsize
for x, y in chicken:
d = abs(i - x) + abs(j - y)
min_ = min(min_, d)
dist += min_
return dist
answer = sys.maxsize
for c in combinations(chicken, M):
answer = min(answer, calc(c))
print(answer)