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

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

15686번: 치킨 배달

 

알고리즘 설계

 

예제 입력 1 복사

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 복사

5

치킨집 위치 (1, 2) chicken 1 2 house 0 2 치킨집 ~ 집 거리 =  1 치킨집 위치 (2, 2) chicken 2 2 house 0 2 치킨집 ~ 집 거리 =  1 치킨집 위치 (4, 4) chicken 4 4 house 0 2 치킨집 ~ 집 거리 =  1 1 치킨집 위치 (1, 2) chicken 1 2 house 1 4 치킨집 ~ 집 거리 =  2 치킨집 위치 (2, 2) chicken 2 2 house 1 4 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 4) chicken 4 4 house 1 4 치킨집 ~ 집 거리 =  2 3 치킨집 위치 (1, 2) chicken 1 2 house 2 1 치킨집 ~ 집 거리 =  2 치킨집 위치 (2, 2) chicken 2 2 house 2 1 치킨집 ~ 집 거리 =  1 치킨집 위치 (4, 4) chicken 4 4 house 2 1 치킨집 ~ 집 거리 =  1 4 치킨집 위치 (1, 2) chicken 1 2 house 3 2 치킨집 ~ 집 거리 =  2 치킨집 위치 (2, 2) chicken 2 2 house 3 2 치킨집 ~ 집 거리 =  1 치킨집 위치 (4, 4) chicken 4 4 house 3 2 치킨집 ~ 집 거리 =  1 5

치킨집 ~ 집거리 최솟값 : 5

——————————————————————————————

예제 입력 2 복사

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

예제 출력 2 복사

10

 

치킨집 위치 (0, 1) chicken 0 1 house 0 3 치킨집 ~ 집 거리 =  2 치킨집 위치 (3, 0) chicken 3 0 house 0 3 치킨집 ~ 집 거리 =  2 2 치킨집 위치 (0, 1) chicken 0 1 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (3, 0) chicken 3 0 house 1 0 치킨집 ~ 집 거리 =  2 4 치킨집 위치 (0, 1) chicken 0 1 house 1 2 치킨집 ~ 집 거리 =  2 치킨집 위치 (3, 0) chicken 3 0 house 1 2 치킨집 ~ 집 거리 =  2 6 치킨집 위치 (0, 1) chicken 0 1 house 3 3 치킨집 ~ 집 거리 =  5 치킨집 위치 (3, 0) chicken 3 0 house 3 3 치킨집 ~ 집 거리 =  3 9 치킨집 위치 (0, 1) chicken 0 1 house 3 4 치킨집 ~ 집 거리 =  6 치킨집 위치 (3, 0) chicken 3 0 house 3 4 치킨집 ~ 집 거리 =  4 13 치킨집 위치 (0, 1) chicken 0 1 house 4 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (3, 0) chicken 3 0 house 4 3 치킨집 ~ 집 거리 =  4 17

치킨집 위치 (0, 1) chicken 0 1 house 0 3 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 0) chicken 4 0 house 0 3 치킨집 ~ 집 거리 =  2 2 치킨집 위치 (0, 1) chicken 0 1 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 0) chicken 4 0 house 1 0 치킨집 ~ 집 거리 =  2 4 치킨집 위치 (0, 1) chicken 0 1 house 1 2 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 0) chicken 4 0 house 1 2 치킨집 ~ 집 거리 =  2 6 치킨집 위치 (0, 1) chicken 0 1 house 3 3 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 0) chicken 4 0 house 3 3 치킨집 ~ 집 거리 =  4 10 치킨집 위치 (0, 1) chicken 0 1 house 3 4 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 0) chicken 4 0 house 3 4 치킨집 ~ 집 거리 =  5 15 치킨집 위치 (0, 1) chicken 0 1 house 4 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 0) chicken 4 0 house 4 3 치킨집 ~ 집 거리 =  3 18

치킨집 위치 (0, 1) chicken 0 1 house 0 3 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 1) chicken 4 1 house 0 3 치킨집 ~ 집 거리 =  2 2 치킨집 위치 (0, 1) chicken 0 1 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 1) chicken 4 1 house 1 0 치킨집 ~ 집 거리 =  2 4 치킨집 위치 (0, 1) chicken 0 1 house 1 2 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 1) chicken 4 1 house 1 2 치킨집 ~ 집 거리 =  2 6 치킨집 위치 (0, 1) chicken 0 1 house 3 3 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 1) chicken 4 1 house 3 3 치킨집 ~ 집 거리 =  3 9 치킨집 위치 (0, 1) chicken 0 1 house 3 4 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 1) chicken 4 1 house 3 4 치킨집 ~ 집 거리 =  4 13 치킨집 위치 (0, 1) chicken 0 1 house 4 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 1) chicken 4 1 house 4 3 치킨집 ~ 집 거리 =  2 15

치킨집 위치 (0, 1) chicken 0 1 house 0 3 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 4) chicken 4 4 house 0 3 치킨집 ~ 집 거리 =  2 2 치킨집 위치 (0, 1) chicken 0 1 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 4) chicken 4 4 house 1 0 치킨집 ~ 집 거리 =  2 4 치킨집 위치 (0, 1) chicken 0 1 house 1 2 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 4) chicken 4 4 house 1 2 치킨집 ~ 집 거리 =  2 6 치킨집 위치 (0, 1) chicken 0 1 house 3 3 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 4) chicken 4 4 house 3 3 치킨집 ~ 집 거리 =  2 8 치킨집 위치 (0, 1) chicken 0 1 house 3 4 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 4) chicken 4 4 house 3 4 치킨집 ~ 집 거리 =  1 9 치킨집 위치 (0, 1) chicken 0 1 house 4 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 4) chicken 4 4 house 4 3 치킨집 ~ 집 거리 =  1 10

치킨집 위치 (3, 0) chicken 3 0 house 0 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 0) chicken 4 0 house 0 3 치킨집 ~ 집 거리 =  6 6 치킨집 위치 (3, 0) chicken 3 0 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 0) chicken 4 0 house 1 0 치킨집 ~ 집 거리 =  2 8 치킨집 위치 (3, 0) chicken 3 0 house 1 2 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 0) chicken 4 0 house 1 2 치킨집 ~ 집 거리 =  4 12 치킨집 위치 (3, 0) chicken 3 0 house 3 3 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 0) chicken 4 0 house 3 3 치킨집 ~ 집 거리 =  3 15 치킨집 위치 (3, 0) chicken 3 0 house 3 4 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 0) chicken 4 0 house 3 4 치킨집 ~ 집 거리 =  4 19 치킨집 위치 (3, 0) chicken 3 0 house 4 3 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 0) chicken 4 0 house 4 3 치킨집 ~ 집 거리 =  3 22

치킨집 위치 (3, 0) chicken 3 0 house 0 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 1) chicken 4 1 house 0 3 치킨집 ~ 집 거리 =  6 6 치킨집 위치 (3, 0) chicken 3 0 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 1) chicken 4 1 house 1 0 치킨집 ~ 집 거리 =  2 8 치킨집 위치 (3, 0) chicken 3 0 house 1 2 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 1) chicken 4 1 house 1 2 치킨집 ~ 집 거리 =  4 12 치킨집 위치 (3, 0) chicken 3 0 house 3 3 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 1) chicken 4 1 house 3 3 치킨집 ~ 집 거리 =  3 15 치킨집 위치 (3, 0) chicken 3 0 house 3 4 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 1) chicken 4 1 house 3 4 치킨집 ~ 집 거리 =  4 19 치킨집 위치 (3, 0) chicken 3 0 house 4 3 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 1) chicken 4 1 house 4 3 치킨집 ~ 집 거리 =  2 21

치킨집 위치 (3, 0) chicken 3 0 house 0 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 4) chicken 4 4 house 0 3 치킨집 ~ 집 거리 =  5 5 치킨집 위치 (3, 0) chicken 3 0 house 1 0 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 4) chicken 4 4 house 1 0 치킨집 ~ 집 거리 =  2 7 치킨집 위치 (3, 0) chicken 3 0 house 1 2 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 1 2 치킨집 ~ 집 거리 =  4 11 치킨집 위치 (3, 0) chicken 3 0 house 3 3 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 4) chicken 4 4 house 3 3 치킨집 ~ 집 거리 =  2 13 치킨집 위치 (3, 0) chicken 3 0 house 3 4 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 3 4 치킨집 ~ 집 거리 =  1 14 치킨집 위치 (3, 0) chicken 3 0 house 4 3 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 4 3 치킨집 ~ 집 거리 =  1 15

치킨집 위치 (4, 0) chicken 4 0 house 0 3 치킨집 ~ 집 거리 =  7 치킨집 위치 (4, 1) chicken 4 1 house 0 3 치킨집 ~ 집 거리 =  6 6 치킨집 위치 (4, 0) chicken 4 0 house 1 0 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 1) chicken 4 1 house 1 0 치킨집 ~ 집 거리 =  3 9 치킨집 위치 (4, 0) chicken 4 0 house 1 2 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 1) chicken 4 1 house 1 2 치킨집 ~ 집 거리 =  4 13 치킨집 위치 (4, 0) chicken 4 0 house 3 3 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 1) chicken 4 1 house 3 3 치킨집 ~ 집 거리 =  3 16 치킨집 위치 (4, 0) chicken 4 0 house 3 4 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 1) chicken 4 1 house 3 4 치킨집 ~ 집 거리 =  4 20 치킨집 위치 (4, 0) chicken 4 0 house 4 3 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 1) chicken 4 1 house 4 3 치킨집 ~ 집 거리 =  2 22

치킨집 위치 (4, 0) chicken 4 0 house 0 3 치킨집 ~ 집 거리 =  7 치킨집 위치 (4, 4) chicken 4 4 house 0 3 치킨집 ~ 집 거리 =  5 5 치킨집 위치 (4, 0) chicken 4 0 house 1 0 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 4) chicken 4 4 house 1 0 치킨집 ~ 집 거리 =  3 8 치킨집 위치 (4, 0) chicken 4 0 house 1 2 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 4) chicken 4 4 house 1 2 치킨집 ~ 집 거리 =  5 13 치킨집 위치 (4, 0) chicken 4 0 house 3 3 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 3 3 치킨집 ~ 집 거리 =  2 15 치킨집 위치 (4, 0) chicken 4 0 house 3 4 치킨집 ~ 집 거리 =  5 치킨집 위치 (4, 4) chicken 4 4 house 3 4 치킨집 ~ 집 거리 =  1 16 치킨집 위치 (4, 0) chicken 4 0 house 4 3 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 4) chicken 4 4 house 4 3 치킨집 ~ 집 거리 =  1 17

치킨집 위치 (4, 1) chicken 4 1 house 0 3 치킨집 ~ 집 거리 =  6 치킨집 위치 (4, 4) chicken 4 4 house 0 3 치킨집 ~ 집 거리 =  5 5 치킨집 위치 (4, 1) chicken 4 1 house 1 0 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 1 0 치킨집 ~ 집 거리 =  4 9 치킨집 위치 (4, 1) chicken 4 1 house 1 2 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 1 2 치킨집 ~ 집 거리 =  4 13 치킨집 위치 (4, 1) chicken 4 1 house 3 3 치킨집 ~ 집 거리 =  3 치킨집 위치 (4, 4) chicken 4 4 house 3 3 치킨집 ~ 집 거리 =  2 15 치킨집 위치 (4, 1) chicken 4 1 house 3 4 치킨집 ~ 집 거리 =  4 치킨집 위치 (4, 4) chicken 4 4 house 3 4 치킨집 ~ 집 거리 =  1 16 치킨집 위치 (4, 1) chicken 4 1 house 4 3 치킨집 ~ 집 거리 =  2 치킨집 위치 (4, 4) chicken 4 4 house 4 3 치킨집 ~ 집 거리 =  1 17

치킨집 ~ 집거리 최솟값 : 10

—————————————————————————————

예제 입력 3 복사

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

예제 출력 3 복사

11

 

 

치킨집 위치 (0, 1) chicken 0 1 house 0 0 치킨집 ~ 집 거리 =  1 1 치킨집 위치 (0, 1) chicken 0 1 house 1 0 치킨집 ~ 집 거리 =  2 3 치킨집 위치 (0, 1) chicken 0 1 house 2 0 치킨집 ~ 집 거리 =  3 6 치킨집 위치 (0, 1) chicken 0 1 house 3 0 치킨집 ~ 집 거리 =  4 10 치킨집 위치 (0, 1) chicken 0 1 house 4 0 치킨집 ~ 집 거리 =  5 15

치킨집 위치 (1, 1) chicken 1 1 house 0 0 치킨집 ~ 집 거리 =  2 2 치킨집 위치 (1, 1) chicken 1 1 house 1 0 치킨집 ~ 집 거리 =  1 3 치킨집 위치 (1, 1) chicken 1 1 house 2 0 치킨집 ~ 집 거리 =  2 5 치킨집 위치 (1, 1) chicken 1 1 house 3 0 치킨집 ~ 집 거리 =  3 8 치킨집 위치 (1, 1) chicken 1 1 house 4 0 치킨집 ~ 집 거리 =  4 12

치킨집 위치 (2, 1) chicken 2 1 house 0 0 치킨집 ~ 집 거리 =  3 3 치킨집 위치 (2, 1) chicken 2 1 house 1 0 치킨집 ~ 집 거리 =  2 5 치킨집 위치 (2, 1) chicken 2 1 house 2 0 치킨집 ~ 집 거리 =  1 6 치킨집 위치 (2, 1) chicken 2 1 house 3 0 치킨집 ~ 집 거리 =  2 8 치킨집 위치 (2, 1) chicken 2 1 house 4 0 치킨집 ~ 집 거리 =  3 11

치킨집 위치 (3, 1) chicken 3 1 house 0 0 치킨집 ~ 집 거리 =  4 4 치킨집 위치 (3, 1) chicken 3 1 house 1 0 치킨집 ~ 집 거리 =  3 7 치킨집 위치 (3, 1) chicken 3 1 house 2 0 치킨집 ~ 집 거리 =  2 9 치킨집 위치 (3, 1) chicken 3 1 house 3 0 치킨집 ~ 집 거리 =  1 10 치킨집 위치 (3, 1) chicken 3 1 house 4 0 치킨집 ~ 집 거리 =  2 12

치킨집 위치 (4, 1) chicken 4 1 house 0 0 치킨집 ~ 집 거리 =  5 5 치킨집 위치 (4, 1) chicken 4 1 house 1 0 치킨집 ~ 집 거리 =  4 9 치킨집 위치 (4, 1) chicken 4 1 house 2 0 치킨집 ~ 집 거리 =  3 12 치킨집 위치 (4, 1) chicken 4 1 house 3 0 치킨집 ~ 집 거리 =  2 14 치킨집 위치 (4, 1) chicken 4 1 house 4 0 치킨집 ~ 집 거리 =  1 15

 

치킨집 ~ 집거리 최솟값 : 11

————————————————————————————————————————————————————

동작과정

1. 입력으로 주어진 도시의 크기(N)와 선택해야 할 치킨 집의 개수(M)를 받습니다.
2. 이후 N개의 줄에 걸쳐 도시의 정보를 입력받습니다.
3. 주어진 도시의 정보를 바탕으로 일반 집(house)과 치킨 집(chicken)의 좌표를 저장합니다.
4. itertools 모듈의 combinations 함수를 사용하여 M개의 치킨 집을 선택하는 모든 경우의 수를 계산합니다.
5. 각 경우에 대해 일반 집과 선택된 치킨 집들 사이의 거리를 계산하고, 그 합을 구합니다.
6. 모든 경우에 대한 거리의 합 중 최솟값을 결과값(res)에 저장합니다.
7. 최종적으로 최솟값인 res를 출력합니다.

코드

# 치킨 배달 15686
"""https://www.acmicpc.net/problem/15686"""

from itertools import combinations

N,M = map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(N)]
house = [] # 일반 집
chicken = [] # 치킨 집
res = int(1e9) # 결과값 초기화

# 집과 치킨 집의 좌표 저장
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            house.append((i,j))
        elif arr[i][j] == 2:
            chicken.append((i,j))

# 조합을 이용하여 M개의 치킨 집을 선택하는 경우의 수 계산
for j in combinations(chicken, M):
    total = 0 # 선택된 치킨 집들까지의 거리의 합을 저장할 변수
    # 각 일반 집에 대해 최소 치킨 거리 계산
    for i in house:
        tmp = int(1e9)
        for k in j:
            #print("치킨집 위치", k)
            tmp = min(tmp, abs(k[0]-i[0])+abs(k[1]-i[1])) # 현재 집과 선택된 치킨 집 사이의 거리 계산
            #print("chicken",k[0],k[1])
            #print("house", i[0],i[1])
            #print("치킨집 ~ 집 거리 = ", min(tmp, abs(k[0]-i[0])+abs(k[1]-i[1])))
        total+=tmp # 현재 일반 집에 대한 최소 치킨 거리를 전체 거리에 더함
        #print(total)
    res = min(res, total)
        
print(res)

 

—————————————————————————————————

combination()함수란?

수를 조합해주는 역할을 한다

예를 들어 위 코드에서 combination(chicken, M)을 입력받았다.

여기서 chicken집의 개수를 3개, M을 3이라고 가정하자.

그렇다면 combination(3,2)으로 조합할 수 있는 오름차순 조합은 무엇일까?

(1,2), (1,3), (2,3) 이와같이 3개의 조합식을 만들어주는 역할을 한다.

—————————————————————————————————

int(1e9)란?

변수를 큰숫자인 10억으로 초기화하는 것을 의미합니다.

위와 같은 과정을 거치면 코드의 가독성을 높이고 작성을 간편하게 만들어주는 역할을 합니다.

—————————————————————————————————

이 코드에서 가장 많이 돌아가는 식은?

tmp = min(tmp, abs(k[0]-i[0])+abs(k[1]-i[1]))

• abs(k[0] - i[0])은 현재 일반 집과 선택된 치킨 집의 x 좌표 차이입니다.
• abs(k[1] - i[1])은 현재 일반 집과 선택된 치킨 집의 y 좌표 차이입니다.
• 따라서, abs(k[0] - i[0]) + abs(k[1] - i[1])는 현재 일반 집과 선택된 치킨 집 사이의 거리입니다.

min(tmp, ...)은 현재까지의 최소 거리(tmp)와 새로 계산한 거리 중 더 작은 값을 선택하여 tmp에 저장합니다. 이렇게 하면 현재까지의 최소 거리를 유지하면서 새로운 거리를 고려할 수 있습니다.

이 작업은 각각의 일반 집에 대해 모든 선택된 치킨 집들과의 거리를 비교하여 최소 거리를 구하는 역할을 합니다. 이후에는 이 최소 거리를 total에 더하여 현재 선택된 치킨 집들에 대한 모든 일반 집의 치킨 거리의 합을 계산합니다.

 

위코드의 시간복잡도는 O(C(n, M) * n * M)입니다.