[골드 V] 15686번. 치킨 배달

 문제 

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

15686번: 치킨 배달

 사용 언어 

Python3

 풀이 과정 

일단 이 문제도 그래프 탐색으로 착각하기 좋은 문제였다. 라인에서도 그런 문제가 있었는데... 이중 리스트를 사용하면 무조건 그래프 탐색이라는 편견(?)이 생겨버린 모양이다. 탈출하자

 

문제를 다시 천천히 읽으면서 어떻게 풀지 생각해보니 그냥.. 단순 조합을 이용한 완전 탐색도 가능해보여서 그대로 풀어봤고, 중간에 좀 헷갈린 부분은 자꾸 답이 너무 크게 나와서 뭐지? 했는데 졸려서 모든 집에 대한 모든 치킨집 거리를 다 더해버리는 코드를 짰던거였다...ㅎㅎ 그 부분만 제일 가까운 치킨집 거리끼리 더해주는 코드로 변경하니까 바로 맞았습니다!!

근데 사실 조금이라도 효율이 좋을 것 같은 백트래킹으로 풀고 싶었는데 어떻게 풀어야 하는지 감도 안와서 아래에서 다른 분이 푼 코드를 참고하겠다.

 

 제출 답안 

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

# 각 칸은 0빈 칸/1집/2치킨집 중 하나
# 치킨 거리 = 집에서 가장 가까운 치킨집 사이의 거리
# 도시의 치킨 거리 = 모든 집의 치킨 거리의 합
# M개의 치킨집만 남기고 모두 폐업시킬 때, 도시의 치킨 거리가 최솟값이 되도록

# 치킨집마다 집과의 거리를 계산해서 가장 가까운 치킨집 거리를 반환
def nearest(house, stores):
    hx, hy = house
    min_distance = float("inf")
    for sx, sy in stores:
        dist = abs(hx - sx) + abs(hy - sy)
        if dist < min_distance:
            min_distance = dist
    return min_distance

if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = []
    houses = []
    chickens = []
    # 그래프를 입력받으며 집 위치와 치킨집 위치를 튜플로 저장
    for i in range(N):
        line = list(map(int, input().split()))
        for j in range(N):
            if line[j] == 1:
                houses.append((i, j))
            if line[j] == 2:
                chickens.append((i, j))
        graph.append(line)

    answer = []
    # M개의 치킨집으로 가능한 조합들을 돌며 도시의 치킨 거리들을 저장
    for stores in combinations(chickens, M):
        city_chicken_dist = 0
        for house in houses:
            city_chicken_dist += nearest(house, stores)
        answer.append(city_chicken_dist)
    # 그 중 최솟값 출력
    print(min(answer))

 

 다른 사람 코드 

1. 백트래킹

# 치킨 배달
# 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리
# 도시의 치킨 거리는 모든 집의 치킨 거리의 합

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

house_list = []
chicken_list = []
choosen_chicken_list = []
answer = 1000000 # 임의의 숫자
# 치킨집, 집 위치 값 넣기
for i in range(N):
    for j in range(N):
        if graph[i][j] == 2:
            chicken_list.append((i,j))
        if graph[i][j] == 1:
            house_list.append((i,j))

# dfs 구현
def dfs(depth, idx):
    global answer
    if depth == M:
        sum = 0
        for house in house_list: # 하우스 당 체크 시작
            val = 1000000 # 임의의 숫자
            for choosen_chicken in choosen_chicken_list: # 치킨집 순차 탐색
                tmp = abs(house[0]-choosen_chicken[0]) + abs(house[1]-choosen_chicken[1]) # 치킨 거리
                val = min(tmp, val) # 각 house 당 치킨 거리의 최소 값  = val
            sum += val # 도시의 치킨 거리 = val의 합 = 각 house 당 치킨 거리의 최소 값의 합
        answer = min(answer, sum)  
        return

    for i in range(idx, len(chicken_list)): # combination 구현
        if chicken_list[i] in choosen_chicken_list:
            continue
        
        choosen_chicken_list.append(chicken_list[i])
        dfs(depth+1, i+1)
        choosen_chicken_list.pop()
        
dfs(0, 0)
print(answer)

➡ 백트래킹의 핵심인 뭘 append했다가 pop하는지가 궁금했는데 가능한 M개의 식당 조합을 그렇게 찾는거였다. 그래서 결국 combination을 구현한다는 건 똑같은데 dfs로 구현하기 때문에 오히려 시간이 더 걸린다..! 백트래킹이 구현보다 항상 빠를 거라는 생각은 틀렸구만... 

 

 

2. 스터디원의 코드

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

citySize, limitCH = map(int, input().split())

chickenDistanceInfo = {}
chickenInfo = []
houseInfo = []

# 치킨집이랑 일반집 담아주기
for i in range(1, citySize+1):
    rowInfo = list(map(int, input().split()))
    for colIndex in range(1, citySize+1):
        if rowInfo[colIndex-1] == 1:
            houseInfo.append((i, colIndex))
        elif rowInfo[colIndex-1] == 2:
            chickenInfo.append((i, colIndex))

# 치킨거리 표 만들기 예시는 아래 주석에!
for chickenZip in chickenInfo:
    cR, cC = chickenZip
    chickenDistanceInfo[chickenZip] = []
    for house in houseInfo:
        hR, hC = house
        chickenDistance = abs(cR-hR) + abs(cC-hC)
        chickenDistanceInfo[chickenZip].append(chickenDistance)

# print(chickenDistanceInfo)
# 행은 치킨집, 열은 일반집
# {      (1, 3)(2, 5)(3, 2)(4, 3)
# (2, 3): [1,    2,    2,    2], 
# (3, 3): [2,    3,    1,    1], 
# (5, 5): [6,    3,    5,    3]}

# chickenDistanceInfo dictionary 형태로 들어가면 치킨 거리 구해주는 함수
def calculateChickenDistance(info):
    totalDistance = 0
    for i in range([len(value) for key, value in info.items()][0]):
        minDistanceEachHouse = float('inf')
        for key, value in info.items():
            if value[i] < minDistanceEachHouse:
                minDistanceEachHouse = value[i]
        totalDistance += minDistanceEachHouse
    return totalDistance

# 만약 있어야 하는 치킨집 개수가 현재 치킨집 개수와 같으면 바로 치킨 거리 구하기
if len(chickenDistanceInfo) == limitCH:
    print(calculateChickenDistance(chickenDistanceInfo))
# 현재 치킨집 개수가 더 많으면 조합으로 최소 거리를 가지는 경우 구하기
else:
    minChickenDistance = float('inf')
    # 치킨집이 5개이고, 있어야하는 수가 2면 5Comnibation2
    for selectedChickenHouses in combinations(chickenInfo, limitCH):
        selectedChickenInfo = {}
        # 뽑힌 치킨집들 가지고 info 만들기
        for chickenHouse in selectedChickenHouses:
            selectedChickenInfo[chickenHouse] = chickenDistanceInfo[chickenHouse]
        # 만든 info로 치킨 거리 구하기
        tempMinValue = calculateChickenDistance(selectedChickenInfo)
        # 최솟값 갱신해주기
        if tempMinValue < minChickenDistance:
            minChickenDistance = tempMinValue
    print(minChickenDistance)

➡ 내가 본 코드 중에 가장 빨랐던 방법! 딕셔너리를 사용하는 방법은 생각도 못했는데 독창적으로 잘 푸신 것 같고 그렇게 치킨집을 기준으로 각각 일반집에 해당하는 치킨거리를 저장해둬서 완전탐색을 하면서 거리를 여러 번 계산하는 과정이 줄어들어 시간도 줄어든 것 같다👍

 

출처 : https://velog.io/@blcklamb/%EB%B0%B1%EC%A4%80Python-15686%EB%B2%88-%EC%B9%98%ED%82%A8-%EB%B0%B0%EB%8B%AC