[백준] 15686 치킨 배달

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

치킨집을 기준으로 하여 각 치킨집에서 집까지 치킨 거리를 모두 구하여 2차원 배열로 저장하도록 했습니다.

치킨집을 최대한 M개 모두 사용하는것이 도시의 치킨 거리를 가장 작게 만들 수 있으므로, M개 모두 선택했을때의 조합을 구하였습니다.

미리 구해둔 2차원 배열을 이용해, 각 집과 치킨집의 최소 거리를 찾아서 도시의 치킨거리의 최솟값을 구했습니다.

2) 알고리즘

• 브루트포스

3) 풀이 코드

사용 언어 - Python

import sys
from itertools import combinations
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())                               # 도시의 크기, 최대 치킨집의 개수
city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]     # 도시의 정보 / 0-빈칸, 1-집, 2-치킨집

chicken = []        # 치킨집의 좌표들
home = []           # 집의 좌표들
answer = 1e10       # 도시의 치킨 거리, 초기에 임의의 큰 값

for i in range(N):                      # 도시를 한번 확인하여, 치킨집과 집의 좌표들을 모두 구함
    for j in range(N):
        if city[i][j] == 1:
            home.append((i+1, j+1))
        elif city[i][j] == 2:
            chicken.append((i+1, j+1))

dist = [[0] * len(home) for _ in range(len(chicken))]       # 각 치킨집별 집까지의 치킨 거리 / 행-치킨집의 번호, 열-집의 번호

for i in range(len(chicken)):
    for j in range(len(home)):
        dist[i][j] = abs(chicken[i][0] - home[j][0]) + abs(chicken[i][1] - home[j][1])  # i번째 치킨집과 j번째 집의 치킨 거리를 구하여 저장

for comb in combinations(range(len(chicken)), M):       # 조합을 이용하여 치킨집을 M개 선택
    tmp = 0                                             # 현재 경우의 도시의 치킨 거리
    for h in range(len(home)):                          # 모든 집의 치킨 거리를 구해야 함
        min_dist = 1e10
        for c in comb:                                  
            min_dist = min(min_dist, dist[c][h])        # 선택한 치킨 거리와 이전의 치킨 거리 중 최솟값을 저장 
        tmp += min_dist                                 # 도시의 치킨 거리에 현재 집의 치킨 거리 추가

        if tmp >= answer:           # 탐색하던 중 기존에 구해둔 도시의 치킨 거리 보다 큰 값이면, 이후에 찾아도 의미 없으므로 종료
            break
    else:
        answer = tmp                # 도시의 치킨 거리 최솟값 갱신
        
print(answer)                       # 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

15686번: 치킨 배달

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다