[Python]🥇 15686번 치킨 배달 / 조합과 3중 for문을 이용한 풀이 및 문제 해설

 

예제 입력 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

예제 입력 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

예제 입력 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

문제 해석

치킨집을 m개 골랐을 때, 각 집(1)에서 가장 가까운 치킨거리를 찾고 그걸 모두 더해라!  그 중 가장 작은 값을 골라라 

즉, 1에서 갈 수 있는 가장 가까운 2와의 거리를 찾고 그걸 모두 합하는 구현 문제!

또한 문제 범위가 작고, 그 중 m개를 선택한다면 조합을 떠올리자!

치킨집의 위치가 (x1, y1)이고 집의 위치가 (x2,y2)일 때,

치킨거리 = abs(x1-x2) + abs(y1-y2)

 

 

 

문제 알고리즘

 

(1) input을 받는다

(2) 1과 2의 좌표를 각각 배열(chicken, home)에 저장한다

(3) 치킨집 좌표 m개 고른 모든 조합을 만들고

# [([1, 2], [3, 4]), 
# ([1, 2], [5, 6]), 
# ([3, 4], [5, 6])]

(4) 모든 집에서 가장 가까운 치킨집까지의 거리의 합 중 최솟값을 구한다

 

 

 

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

chicken = []
home = []

#치킨집과 집의 위치를 각각 저장
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            home.append((i,j))
        elif arr[i][j] == 2:
            chicken.append((i,j))

answer = 9999 #min으로 최소값을 결정할 때, 큰 값으로 초기화 하자
com = list(combinations(chicken, m)) #chicken에서 m개의 원소를 뽑는 모든 경우의 수
# [([1, 2], [3, 4]), 
# ([1, 2], [5, 6]), 
# ([3, 4], [5, 6])]

for chi in com: # 첫 번째 "치킨집의 조합"부터 시작
    res = 0 # 각 집에서 가장 가까운 치킨 거리의 합을 저장할 변수
    for x1, y1 in house: # 첫 번째 집부터 시작
        street = 9999 # 각 집에서 가장 가까운 치킨 거리를 저장할 변수
        for x, y2 in chi: # 첫 번째 치킨집부터 시작
            street = min(street, abs(x1-x2) + abs(y1-y2)) # 현재 집과 각 치킨집 사이의 거리를 계산하고, 그 중 가장 가까운 치킨집 거리 선택
        res += street # 각 집에서 가장 가까운 치킨 거리를 모두 더함
    answer = min(answer, res) # 모든 집에서 가장 가까운 치킨 거리의 합 중, 최솟값을 선택

print(answer)

이중 for문도 헷갈려 죽겠는데 삼중 for문은 더 헷갈린다.

자세한 예시를 통해 이해를 해보자 도움은 지피티에게 좀 받았다...^^ 

우선, 다음과 같은 예시 값을 가정하자. 

1. 치킨집 위치(com): [(2, 2), (3, 5)]
2. 집 위치(house): [(1, 1), (2, 3), (4, 2)]

우리가 계산하려는 것은 모든 집에서 가장 가까운 치킨집까지의 거리의 합 중, 최솟값

 

for chi in com: # 첫 번째 "치킨집의 조합"부터 시작
    res = 0 # 각 집에서 가장 가까운 치킨 거리의 합을 저장할 변수
    for x1, y1 in house: # 첫 번째 집부터 시작
        street = 9999 # 각 집에서 가장 가까운 치킨 거리를 저장할 변수
        for x, y2 in chi: # 첫 번째 치킨집부터 시작
            street = min(street, abs(x1-x2) + abs(y1-y2)) # 현재 집과 각 치킨집 사이의 거리를 계산하고, 그 중 가장 가까운 치킨집 거리 선택
        res += street # 각 집에서 가장 가까운 치킨 거리를 모두 더함
    answer = min(answer, res) # 모든 집에서 가장 가까운 치킨 거리의 합 중 최솟값을 선택

예를 들어 첫 번째 치킨집 (2, 2)를 선택했을 때,

• 첫 번째 집1, 1)은 치킨집까지의 거리가 2이고,
• 두 번째 집 (2, 3)은 치킨집까지의 거리가 1이며,
• 세 번째 집 (4, 2)는 치킨집까지의 거리가 2이다. 

따라서, 첫 번째 치킨집을 선택했을 때의 거리의 합은 2+1+2=5

동일한 방식으로 두 번째 치킨집 (3, 5)를 선택했을 때의 거리의 합을 계산하면,

두 치킨집 중에서 거리의 합이 더 작은 치킨집을 선택하게 된다.

이렇게 해서 모든 치킨집에 대해 계산한 후, 그 중에서 가장 작은 값을 선택하면 된다!

 

느낀점

 

항상 느끼는 거지만.... 백준은 문제가 너무 불친절하다... 

진심 문제에서 뭘 구하라는 건지 이해가 안돼서 3일동안 고민한 적도 많음.... 얼른 레벨업해서 

프로그래머스 풀어야지 :)..