백준 15686번(치킨 배달) 파이썬

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

15686번: 치킨 배달

백트래킹, 구현 문제이다.

문제를 보고 "오? 할만한데?" 생각으로 덤볐다. 근데 막 좌절한 정도는 아니고 for문이 많이 들어가다 보니까 순서를 잡고 어느 for문에서 변수를 초기화 하는지를 생각하는게 오래 걸렸다.

결론적으로 "할만했다"

앞으로 난이도가 높은 문제에 자주 부딪힐 생각이다. 취준이 얼마남지 않았기 때문이다...

아래는 풀이 코드와 설명이다.

import sys
import itertools
input = sys.stdin.readline

n,m = map(int,input().split())
graph = []
chicken = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

for i in range(n): # 치킨집 좌표를 찾아주는 for문 입니다.
    for j in range(n):
        if graph[i][j] == 2:
            chicken.append((i,j))
        
final_chicken = list(itertools.combinations(chicken,m)) # 남아 있어야 하는 치킨집의 경우의 수를 구합니다.

tmp = []
for x in final_chicken: # 남아있는 치킨집에 대해 치킨거리가 가장낮은 경우를 찾아줍니다.
    distance = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1: # 집을 발견했을때
                value = 10e9
                for a in x:# 예제 1의 경우 x = [(1,2),(2,2),(4,4)]로 되어 있으므로 집들을 앞의 3개의 치킨집에 계산해 가장 낮은 치킨거리를 찾는다
                    total=abs(i-a[0])+abs(j-a[1])
                    value = min(total,value)
                distance+=value #distance라는 변수에 모든 집의 치킨거리를 더해줘 해당 경우의 수가 갖는 최소 치킨거리를 tmp리스트에 넣어준다.
    tmp.append(distance)
print(min(tmp)) # 모든 경우의 수의 가장낮은 치킨거리를 출력해준다!