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

solved.ac 난이도 :  GOLD5

백준  15686번- 파이썬 풀이 (삼성전자  sw역량테스트)

 

<문제>

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

15686번: 치킨 배달

<풀이>-구현,브루트포스 알고리즘

• 이 문제는 경우의 수를 사용하면 어렵지 않게 풀 수 있는 문제다.
• 각 집을 기준으로 거리가 가장가까운 치킨집을 구한후(치킨거리) 그 거리들을 더해주면 된다.(도시의 치킨거리)
• 이때 어떤 치킨집을 선택하느냐에 따라 도시의 치킨거리 값이 달라진다.
• 따라서 모든 경우의 도시의 치킨거리를 구한 후 그 중 최솟값을 구하면 된다.

치킨집을 고르는 경우의 수 : from itertools import combinations를 통해 구한다.

모든 경우의 수에서 도시의 치킨거리를 구하기 위해 삼중반복문을 사용한다.

for candidate in chicken_s:
    city_dist =0
    for j in range(len(city)):
        dist =10000
        for x,y in candidate:
            dist = min(dist,abs(x-city[j][0])+abs(y-city[j][1]))
        city_dist+=dist
    ans = min(ans,city_dist)

chicken_s : 어떤 치킨집을 고르는지에 대한 모든 경우의 수가 담겨있는 배열

candidate : 현재 선택된 치킨집의 위치

dist : 각 집의 위치로부터 현재 선택된 치킨집까지의 최소 거리(치킨거리)

city_dist : 각 집에서의 치킨거리를 합한 도시의 치킨거리

ans : 현재 선택된 치킨집에서 나온 도시의 치킨거리, 만약 다른 candidate에서 더 거리가 짧은 값이 나오면 그 값으로 갱신된다.

<코드>-파이썬

from itertools import combinations
n,m = map(int,input().split())
data = []
chicken = []
city = []
for _ in range(n):
    data.append(list(map(int,input().split())))
for i in range(n):
    for j in range(n):
        if data[i][j] == 1:
            city.append((i,j))
        if data[i][j] == 2:
            chicken.append((i,j))
ans = 10000
chicken_s = list(combinations(chicken,m))
for candidate in chicken_s:
    city_dist =0
    for j in range(len(city)):
        dist =10000
        for x,y in candidate:
            dist = min(dist,abs(x-city[j][0])+abs(y-city[j][1]))
        city_dist+=dist
    ans = min(ans,city_dist)

print(ans)

-마치며-

문제의 해결아이디어를 떠올리는데는 큰 어려움이 없었다. 하지만 그 아이디어를 코드로 구현하는데 약갼의 어렴을 겪었다.

필자는 반복문을 작성할때 

for x,y in candidate를 먼저 쓰고 for j in range(len(city))를 마지막에 작성했다.

하지만 이렇게 치킨집이 기준이 될경우

치킨집과 집의 치킨거리보다 더 짧은 거리를 갖는 치킨집을 배제하기 때문에 문제를 틀리게 된다.

따라서 반복문을 작성할때 무엇이 기준인지를 확실하게 이해해야 한다.