[ 백준 브루트포스 ] 15686 치킨 배달

🥕 [ 백준 15686 ] 치킨 배달

문제 링크

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

15686번: 치킨 배달

 

🍒 문제 분석

N * N 맵이 주어지고, 그 위에 집과 치킨집이 있다.

치킨집 중 M개 빼고 나머지는 다 폐업 시킨다고 할 때,

각 집에서 가장 가까운 치킨집과의 거리들의 합이 최솟값이 되게 할 때

그 최솟값을 구하는 문제이다.

 

치킨집과 집과의 거리는 다음과 같다.

: abs( r1 - r2 ) + abs( c1 - c2 )

 

🥑 코드

N, M = map(int,input().split())
graph = [input().split() for _ in range(N)]
house = []
chicken = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == '1' :
            house.append([i,j])
        if graph[i][j] == '2' :
            chicken.append([i,j])

리스트에 집의 위치와 치킨집의 위치를 담았다.

 

from itertools import combinations

ans = 99999999
for chi in combinations(chicken,M):
    distance = 0
    for i in range(len(house)):
        dis = 99999999
        for j in range(M):
            tmp =  abs(chi[j][0]-house[i][0]) + abs(chi[j][1]-house[i][1])
            if tmp < dis :
                dis = tmp
        distance += dis
    if ans > distance:
        ans = distance
print(ans)

 

 

🍓 내 해결 과정

1. 브루트 포스라는게 바로 눈에 안보였다.

그래프 N*N 에서 N은 최대 50까지

치킨집 중 남는 M은 최대 13까지

집의 갯수는 최대 2N개 이다.

 

N이 50, M이 13 이라고 하면,

집의 갯수 2N개에 대해 각각 모든 치킨집과의 거리를 계산한다고 하면 연산은 총

100 * 13 = 1300 회 이다.

 

하지만 M개를 뽑는 경우의 수를 또한 고려해주어야하는데

 

2. itertools 라이브러리의 combination이 생각이 나지 않았다.

조합으로 M개를 뽑으면 되는데 생각이 바로 나지 않았고,

DP로 접근하보려고 이리저리 그래프 그림을 그리다가 너무 복잡 한거 같아서 펜을 여러번 놓았다. 

 

치킨집은 최대 13개 까지 존재하므로 13개 중에 13개 뽑는 연산이라 하면 1 이다.

 

따라서 모든 연산 수는 1300회 이다.

 

 

다른 예 )

집의 갯수가 100개, 치킨집 13개 중 7개를 뽑는다고 하면

100 * 7 * \( _{13}C_{7}\) = 700 * 1716 = 1201200 회 이다.

 

3. 파이썬은 1초에 2천만번 연산 을 수행하면 된다고 보면 된다.

 

따라서 백만 정도 되는 연산은 당연하게도 브루트 포스로 해결 가능하다.

 

문제 아이디어만 알면 코드 구현은 크게 어렵지 않았다.

 

 

🍉 깨달은 점 및 정리

 

1. 파이썬 연산이 1초에 2천만번 인걸 항상 기억하자

 

2. N개 중 M개를 뽑는, 그런 경우의 수를 세는 문제가 아닌지 눈여겨 보자.

 

3. 이상하게 조합 나오는 문제는 조합을 쓰면 된다는걸 떠올리지 못해서 틀리는 것 같다.

지금이 세 번째인거 같은데. 앞으로는 그러지 않길 바란다.