[백준 15686] 치킨배달 Python 코드

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

백준의 15686 치킨배달은 삼성 SW역량테스트 A형 기출문제로 출제되었다. 

 

문제는 N * N 크기의 도시에서 빈칸, 치킨집, 집 중 하나로 구성되어 있을 때, 집과 치킨집의 거리를 계산하여 도시에 있는 치킨집 중 치킨 거리가 가장 작게 될 지 구하는 프로그램을 작성하는 문제이다. 

 

입력 : 첫째 줄에 N(2 <= N <= 50)과 M(1<= M<=13) 이 주어진다. 둘째 줄 부터 N개의 줄에는 도시 정보가 주어진다. 

도시정보

- 0 : 빈칸

- 1 : 집 

- 2 : 치킨집 

출력 : 첫째 줄에 폐업시키지 않을 치킨집 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력

 

[문제풀이] 

1. 아직 코딩테스트 입문자라 처음 지도를 보고서는 구현 종류의 문제인줄 알았으나, 완전 탐색 문제(재귀함수)인 것을 생각해냈다.

2.  우선 치킨 집과 집 간의 거리를 계산해야 하는 함수와 치킨 집을 고른 개수가 m일 때 조건을 주어 모든 집과 치킨 집 사이의 최단 거리를 구한 후 반환하는 함수 두 개를 구현해야 한다. 

 

# 도시의 크기, 치킨 집 개수를 입력받음 
n,m = map(int, input().split())
# 도시 구조에 대한 정보를 입력받음 
City = [list(map(int, input().split())) for _ in range(n)]

def Brute_Force(idx, x, y): 
    global answer
    if(idx == m):
        choice_chicken = []
        for i in range(n):
            for j in range(n):
                if(City[i][j] == 3):
                    choice_chicken.append((i,j))
        res = Min_Distance(choice_chicken, house)
        if(answer > sum(res)):
            answer = sum(res)
        return 
    else:
        for i in range(x, n):
            if(i == x): k = y 
            else: k = 0
            for j in range(k,n):
                if(City[i][j] == 2):
                    City[i][j] = 3
                    Brute_Force(idx+1, i, j+1)
                    City[i][j] = 2

def Min_Distance(chicken, house):
    sum_Distance = []
    for i in house:
        min_D = 987654321
        for j in chicken:
            Distance = abs(i[0] - j[0]) + abs(i[1] - j[1])
            min_D = min(min_D, Distance)
        sum_Distance.append(min_D)
    return sum_Distance



answer = 987654321
house = []
for i in range(n):
    for j in range(n):
        if(City[i][j] == 1):
            house.append((i,j))
Brute_Force(0,0,0)
print(answer)