[백준 15686번] 치킨 배달(Python)

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

15686번: 치킨 배달

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

 

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

 

 

문제 풀이

이 문제는 완전 탐색 문제로 다음과 같이 풀이할 수 있다.

 

치킨집 1개일 때 … 최소 치킨 거리 d1

치킨집 2개일 때 … 최소 치킨 거리 d2

…

치킨집 m개일 때 … 최소 치킨 거리 dm 

 

위의 값을 모두 구한 후 가장 작은 값을 선택하면 정답이 된다.

수식으로 나타내면 다음과 같다.

 

코드를 살펴보자.

 

- 치킨 거리를 구하는 함수는 다음과 같이 정의한다.

def get_chicken_distance(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

두 지점의 좌표를 튜플(x, y) 형태로 p1, p2에 받아와 두 지점의 거리를 반환한다.

 

- 처음에는 도시크기, 치킨집개수, 도시 정보를 입력 받아 N, M, map에  각각 저장한다.

N, M = map(int, input().split(' ')) # 도시 크기 N, 치킨 집 개수 M
map = [list(map(int, input().split(' '))) for _ in range(N)] # 도시정보

도시정보 입력에는 python의 list와 map을 이용하여 입력받았다.

 

- 그 후 집에 대한 좌표와 치킨집에 대한 좌표를 저장하는 list를 생성한다.

chicken_list = [(i, j) for i in range(len(map)) for j in range(len(map[i])) if map[i][j] == CHICKEN]
house_list = [(i, j) for i in range(len(map)) for j in range(len(map[i])) if map[i][j] == HOUSE]

list comprehension을 사용하여 튜플 리스트 형태로 저장하였다.

 

- 이제 치킨집이 1개인 경우 부터 M개인 경우까지 모두 치킨거리를 계산하여 최소 거리를 구한다.(완전 탐색)

result = sys.maxsize
for i in range(1, M + 1):
    combination = list(itertools.combinations(chicken_list, i)) # nCr(조합)
    for c in combination:
        city_dist = 0
        # 각 집에 대한 최소 치킨거리를 구하여 city_dist에 더해준다.
        for house in house_list: 
            min_d = min([get_chicken_distance(picked,house) for picked in c]) 
            city_dist += min_d
        #최소 값을 찾은 경우 result에 갱신해준다.
        if city_dist < result: 
            result = city_dist

위의 코드에서 itertools의 combination함수를 사용하여 간단하게 치킨집을 뽑는 경우의 수를 리스트형태로 저장한다.

다음 입력에 대해 combination을 출력해보면 다음과 같다.

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

[((1, 2),), ((2, 2),), ((4, 4),)] #치킨 집을 1개 뽑은 경우
[((1, 2), (2, 2)), ((1, 2), (4, 4)), ((2, 2), (4, 4))] #치킨 집을 2개 뽑은 경우
[((1, 2), (2, 2), (4, 4))] #치킨 집을 3개 뽑은 경우

n개 뽑았을 때의 경우의 수가 튜플리스트 형태로 combination에 저장된다.

그 후 각 집에 대해서 최소 치킨 거리를 구한 후 더해주면 된다.

min_d = min([get_chicken_distance(picked,house) for picked in c])

전체 소스는 다음과 같다.

import itertools, sys, copy

N, M = map(int, input().split(' ')) # 도시 크기 N, 치킨 집 개수 M
map = [list(map(int, input().split(' '))) for _ in range(N)] # 도시정보

BLANK = 0
HOUSE = 1
CHICKEN = 2

chicken_list = [(i, j) for i in range(len(map)) for j in range(len(map[i])) if map[i][j] == CHICKEN]
house_list = [(i, j) for i in range(len(map)) for j in range(len(map[i])) if map[i][j] == HOUSE]

def get_chicken_distance(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


result = sys.maxsize
for i in range(1, M + 1):
    combination = list(itertools.combinations(chicken_list, i))
    print(combination)
    for c in combination:
        city_dist = 0
        for house in house_list:
            min_d = min([get_chicken_distance(picked,house) for picked in c])
            city_dist += min_d
        if city_dist < result:
            result = city_dist

print(result)

 

문제를 잘 통과하는 것을 볼 수 있다.

 

그런데 좀 더 성능을 개선할 수 있을 것 같다.

 

치킨집을 최대 M개 까지 뽑을 수 있기 때문에 1개~M개 뽑을 수 있다.

하지만 무조건적으로 치킨집이 많을 수록 치킨거리는 짧아진다. (각 집에 대해서 제일 가까운 치킨집을 선택할테니까..)

그 말은 치킨 집을 1개~M-1개 뽑았을 경우는 확인하지 않아도 된다는 말이다.

-> 치킨집이 M개 있을 때  M개 뽑았을 경우의 최소거리가 정답!

 

수정된 코드는 다음과 같다.

import itertools, sys, copy

N, M = map(int, input().split(' ')) # 도시 크기 N, 치킨 집 개수 M
map = [list(map(int, input().split(' '))) for _ in range(N)] # 도시정보

BLANK = 0
HOUSE = 1
CHICKEN = 2

chicken_list = [(i, j) for i in range(len(map)) for j in range(len(map[i])) if map[i][j] == CHICKEN]
house_list = [(i, j) for i in range(len(map)) for j in range(len(map[i])) if map[i][j] == HOUSE]

def get_chicken_distance(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


result = sys.maxsize

combination = list(itertools.combinations(chicken_list, M))
for c in combination:
    city_dist = 0
    for house in house_list:
        min_d = min([get_chicken_distance(picked,house) for picked in c])
        city_dist += min_d
    if city_dist < result:
        result = city_dist

print(result)

 

수정된 소스로 실행하였을 때 메모리는 큰 변화는 없지만 실행 시간이 약 3배 빨라진 것을 확인 할 수 있다.

 

---

원래 알고리즘 풀이를 C++로 하였지만 Python으로 다시 공부해보려고 한다.

어색한 문법들이 많지만 C++ 보단 좀 더 간결하고 보기 좋게 잘 풀리는 것 같다.

(성능은 확실히 C++다..  C++로 위 문제를 풀었을 때 실행시간은 8ms 였다..)