치킨 배달

문제 설명

치킨 집 중 총 m개만을 남겨둔 상태로 도시의 치킨 거리의 최솟값을 구하는 문제다. 문제가 이래저래 복잡하니 백준에 가서 문제 이해를 한 뒤 풀이를 보는 걸 추천한다.

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

15686번: 치킨 배달

문제 풀이

첫 번째 접근

1. 기본적인 셋팅

문제를 풀 때 제일 먼저 생각했던 건 현재 도시에 있는 치킨 집의 위치를 알아야 겠다는 것이었다. 그렇기에 값을 받아 2차원 배열로 돌리면서 2가 있으면 해당 위치를 stores에 넣어주도록 했다. 그 다음은 폐업을 진행할 총 상점의 수였다. 이는 현재 도시의 치킨 집의 수인 len(stores)에다가 m을 빼줬다.

 

그 다음 조합으로 len(stores) C len(stores) - m만큼 폐업을 할 치킨 집 조합을 구해줬다. 여기까지 한다면 각 조합에 있는 치킨 집의 위치를 0으로 만들어 준 다음에 그렇게 만든 그래프를 가지고 도시의 치킨 거리를 구한 다음 최솟 값을 구해주면 된다.

# 처음 도시의 치킨 집의 수를 구하는 코드
for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            stores.append((i, j))

# 폐업해야 할 치킨 집의 수를 구하고 그 만큰 조합을 만들어 주는 코드
results = list(combinations(stores, num))

2. 각 조합 별로 삭제 해주기

각 조합에 있는 치킨 집의 위치를 가지고 임시로 만든 2차원 배열 tmpArr에다가 치킨 집이 폐업했음을 알려주면 된다. 여기서 새로운 조합을 불러올 때마다 tmpArr에 최초의 값을 넣어주면 된다. 그리고 조합에 있는 위치들을 전부 0으로 만들어 줬다면 check를 이용해서 도시의 치킨 거리를 구해 answer와 비교한다.

# 다 살려주겠다는 의미
if num == 0:
    answer = min(check(graph), answer)
else:
    for result in results:
        tmpArr = copy.deepcopy(graph)
        for res in result:
            r, c = res
            tmpArr[r][c] = 0
        answer = min(check(tmpArr), answer)

3. 도시의 치킨 거리 구하기

 

여기서는 arrMin을 이용해서 각 집마다 최소 치킨 거리를 저장하게 한다. 2차원 배열을 돌리면서 치킨 집이 있는지 확인하고 만일 치킨 집이 있을 경우 다시 2차원 배열을 돌리면서 집이 나왔을 때 치킨 거리를 구해주고 현재의 값과 비교해 더 작은 값을 arrMin에 넣어준다.

 

그리고 도시 최소 치킨 거리를 구하기 위해서 arr이 1이라 집인 경우에만 해당 집의 최소 치킨 거리를 더해준다.

# 남은 치킨 가게와 각 집의 최소 거리
def check(arr):
    maxValue = int(1e9)
    arrMin = [[maxValue for _ in range(n)] for _ in range(n)]
    returnMin = 0

    # 치킨 집을 하나 발견하면 해당 치킨 집과 모든 집들 사이의 치킨 거리를 구해서 더 작은 값들을 넣어준다.
    for r1 in range(n):
        for c1 in range(n):
            if arr[r1][c1] == 2:
                for r2 in range(n):
                    for c2 in range(n):
                        if arr[r2][c2] == 1:
                            tmp = (abs(r1 - r2) + abs(c1 - c2))
                            arrMin[r2][c2] = min(arrMin[r2][c2], tmp)

    for i in range(n):
        for j in range(n):
            if arr[i][j] == 1:
                returnMin += arrMin[i][j]

    return returnMin

코드

import sys
import copy
from itertools import combinations

n, m = map(int, sys.stdin.readline().rstrip().split(" "))
graph = []
stores = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split(" "))))

for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            stores.append((i, j))

num = len(stores) - m
results = list(combinations(stores, num))

# 남은 치킨 가게와 각 집의 최소 거리
def check(arr):
    maxValue = int(1e9)
    arrMin = [[maxValue for _ in range(n)] for _ in range(n)]
    returnMin = 0

    # 치킨 집을 하나 발견하면 해당 치킨 집과 모든 집들 사이의 치킨 거리를 구해서 더 작은 값들을 넣어준다.
    for r1 in range(n):
        for c1 in range(n):
            if arr[r1][c1] == 2:
                for r2 in range(n):
                    for c2 in range(n):
                        if arr[r2][c2] == 1:
                            tmp = (abs(r1 - r2) + abs(c1 - c2))
                            arrMin[r2][c2] = min(arrMin[r2][c2], tmp)

    for i in range(n):
        for j in range(n):
            if arr[i][j] == 1:
                returnMin += arrMin[i][j]

    return returnMin


answer = int(1e9)

# 다 살려주겠다는 의미
if num == 0:
    answer = min(check(graph), answer)
else:
    for result in results:
        tmpArr = copy.deepcopy(graph)
        for res in result:
            r, c = res
            tmpArr[r][c] = 0
        answer = min(check(tmpArr), answer)

print(answer)