[CLASS 3]백준 15686번 - 치킨 배달

15686번 : 치킨 배달

 

치킨집을 어떻게 닫아야 최대 수익을 유지할 수 있을지에 관한 문제이다. 내가 처음에 고안한 방법은, 치킨집마다 다른 모든 가정집까지의 누적합을 구해서 누적합이 큰 치킨집부터 닫는다는 방법이었다. 그러나 이는 틀린 방법이다.

 

내 코드(오답):

from sys import stdin
input = stdin.readline
from collections import deque

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

# 가정집과 치킨집이 어딘지 저장
for r in range(n):
    for c in range(n):
        if city[r][c] == '1':
            houses.append((r,c))
        elif city[r][c] == '2':
            chickens.append([r,c,0])

# 각각의 치킨집으로부터 떨어진 집들의 거리의 합 저장
for cPos in chickens:
    for hPos in houses:
        cPos[2] += abs(hPos[0]-cPos[0]) + abs(hPos[1]-cPos[1])

# 가까운 집이 많은 치킨집부터 정렬
chickens.sort(key=lambda x: x[2])
for _ in range(len(chickens)-m):
    temp = chickens.pop()
    city[temp[0]][temp[1]] = '0'

# 각각에 집에 대해 BFS로 최단거리 구해서 치킨 거리 계산
cd = 0
dr = [0,0,1,-1]
dc = [1,-1,0,0]
for r,c in houses:
    visited = [[False]*n for _ in range(n)]
    visited[r][c] = True

    queue = deque([(r,c+1),(r+1,c),(r-1,c),(r,c-1)])
    while True:
        tr, tc = queue.popleft()
        if 0<=tr<n and 0<=tc<n:
            if city[tr][tc] == '2':
                cd += abs(tr-r) + abs(tc-c)
                break
            if not visited[tr][tc]:
                visited[tr][tc] = True
                
                for i in range(4):
                    queue.append((tr+dr[i],tc+dc[i]))

print(cd)

 

왜냐하면 단순히 누적합이 가장 크다고해서 해당 치킨집을 없앤다고 도시의 치킨 거리가 가장 적게 줄어든 다는 것을 보장해주지는 않기 때문이다.

이런 반례가 존재한다.

 

 

해당 반례에서 내 코드가 가장 우선시하여 없애야 할 치킨집은 구석의 4개의 치킨집이다. 해당 네 개의 치킨집 중 한 곳을 없앤다면 치킨 거리는 6이다. 그러나 실제로는 중간의 치킨집을 없애야 최소의 치킨 거리 4가 나온다.

 

따라서 이 문제는 브루트 포스로 풀어야 한다. N의 최댓값이 50밖에 안되기 때문에 충분히 가능하다.

 

내 코드:

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

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

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

# 치킨집을 남길 수 있는 조합
comb = list(combinations(chickens,m))
minCD = 1e9

dr = [0,0,1,-1]
dc = [1,-1,0,0]
# 케이스 마다 도시의 치킨 거리를 계산
for case in comb:
    cd = 0
    for house in houses:
        temp = 1e9
        for chicken in case:
            temp = min(temp,abs(house[0]-chicken[0])+abs(house[1]-chicken[1]))
        cd += temp

    minCD = min(minCD,cd)

print(minCD)

 

itertools 의 combinations함수를 사용해서 간단하게 치킨집을 M개 고르는 모든 조합을 구할 수 있다. 그 뒤 해당 조합에 대해서 치킨 거리를 구해서 가장 작은 값을 출력하면 된다.