121. [삼성기출17]Python 백준 15686 번 치킨 배달 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 15686 번 치킨 배달 입니다.

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

15686번: 치킨 배달

 

먼저 백준 15686 번 치킨 배달 정답 코드입니다. 설명은 아래에 있습니다.

from itertools import combinations

n, m = map(int, input().split())
city = []
houses = []
chickens = []

#도시 정보 입력
for _ in range(n):
    city.append(list(map(int, input().split())))

#가정집, 치킨집 좌표 저장
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j])

ans = 1e9
for chicken in combinations(chickens, m):#모든 경우의 m개의 치킨집 좌표 리스트
    tmp = 0
    for house in houses: #모든 집의 좌표
        distance = 100
        for chi in chicken: #해당 경우의 치킨집 좌표 리스트
            distance = min((abs(house[0] - chi[0]) + abs(house[1] - chi[1])), distance)
        tmp += distance
    ans = min(ans, tmp)

print(ans)

 

문제 접근

1. 치킨집이 m개보다 적어지면 치킨 거리는 같거나 늘어나므로 m개보다 작은 치킨집은 고려하지 않습니다.

2. combinations를 이용해 가능한 모든 m개의 치킨집의 조합을 구합니다.

3. 모든 치킨집, 집을 비교하며 최소거리를 업데이트 합니다.

 

Python 코드 구현

 

도시 정보를 입력받고, 치킨집, 가정집의 좌표를 저장합니다.

from itertools import combinations

n, m = map(int, input().split())
city = []
houses = []
chickens = []

#도시 정보 입력
for _ in range(n):
    city.append(list(map(int, input().split())))

#가정집, 치킨집 좌표 저장
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j])

 

1. m개의 치킨집을 고르는 모든 경우의 수 속에서 가장 치킨 거리가 짧은 값을 ans에 저장합니다. (첫 번째 for 문)

2. 모든 집을 방문하면서, 해당 경우의 m개 치킨집들을 모두 비교하여 가장 거리가 짧은 값들만을 tmp에 더합니다. (두 번째 for문)

3. tmp와 ans 를 비교하며 더 작은 값을 업데이트 합니다.

(tmp 는 지금 경우의 치킨거리, ans는 지금까지의 경우의 가장 짧은 치킨거리 입니다.)

ans = 1e9
for chicken in combinations(chickens, m):#모든 경우의 m개의 치킨집 좌표 리스트
    tmp = 0
    for house in houses: #모든 집의 좌표
        distance = 100
        for chi in chicken: #해당 경우의 치킨집 좌표 리스트
            distance = min((abs(house[0] - chi[0]) + abs(house[1] - chi[1])), distance)
        tmp += distance
    ans = min(ans, tmp)

 

답을 출력합니다.

print(ans)

 

파이썬 백준 15686 번 치킨 배달 최종 코드입니다. 

from itertools import combinations

n, m = map(int, input().split())
city = []
houses = []
chickens = []

#도시 정보 입력
for _ in range(n):
    city.append(list(map(int, input().split())))

#가정집, 치킨집 좌표 저장
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j])

ans = 1e9
for chicken in combinations(chickens, m):#모든 경우의 m개의 치킨집 좌표 리스트
    tmp = 0
    for house in houses: #모든 집의 좌표
        distance = 100
        for chi in chicken: #해당 경우의 치킨집 좌표 리스트
            distance = min((abs(house[0] - chi[0]) + abs(house[1] - chi[1])), distance)
        tmp += distance
    ans = min(ans, tmp)

print(ans)

 

백준 15686 번 치킨 배달 자세한 설명 및 Python 코드였습니다.

감사합니다.