15686 - 치킨배달

# 도시의 치킨  거리 = 모든 치킨 거리의 합
# 총 치킨집의 개수 - M 의 도시 치킨 거리가 최소값이 되도록
# 0 : 빈칸, 1 : 집, 2 : 치킨집

def chkDistance(graph, house):
    distance = [float("inf")] * len(house)
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 2:
                for idx, home in enumerate(house):
                    distance[idx] = min(distance[idx], abs(home[0]-i) + abs(home[1]-j))

    return sum(distance)

# 치킨집 삭제
def dfs(graph, cnt):
    global minLoad
    if cnt == (chickenCnt - M):
        chickenLoad = chkDistance(graph, house)
        minLoad = min(minLoad, chickenLoad)
        return

    for i in range(N):
        for j in range(N):
            if graph[i][j] == 2:
                graph[i][j] = 0
                dfs(graph, cnt+1)
                graph[i][j] = 2

if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = []; house = []; chickenHouse = []; chickenCnt=0
    for r in range(N):
        temp = list(map(int, input().split()))
        graph.append(temp)
        for c in range(N):
            if temp[c] == 1:
                house.append([r, c])
            if temp[c] == 2:
                chickenCnt+=1
                chickenHouse.append([r, c])
    minLoad = float("inf")
    dfs(graph, 0)
    print(minLoad)

처음에는 DFS 문제로 풀었다.

그런데 마지막 예제에서 시간초과 문제가 발생하는 것이 아닌가!

그래서 최대한 시간을 줄이기 위해 이것저것(if 문 추가로 실행개수를 줄인다던가...) 해보았지만 제자리걸음 이었다 ㅠ.ㅠ

 

결국, 여기저기 검색해보니 itertools의 combinations 를 사용해 조합으로 푼 사람들이 많더라???

 

사실 프로그래머스에서 몇번 combinations를 사용해서 풀다가 시간초과난적이 많아서 잘 사용안했는데... 어쨌든 간만에 combinations를 사용한 문제를 풀어보았다 :)

다음에 또 써먹어봐야지~ 

# 도시의 치킨  거리 = 모든 치킨 거리의 합
# 총 치킨집의 개수 - M 의 도시 치킨 거리가 최소값이 되도록
# 0 : 빈칸, 1 : 집, 2 : 치킨집
from itertools import combinations
import copy

def chkDistance(graph, house):
    distance = [float("inf")] * len(house)
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 2:
                for idx, home in enumerate(house):
                    distance[idx] = min(distance[idx], abs(home[0]-i) + abs(home[1]-j))

    return sum(distance)

# 치킨집 삭제
def removeChickenHouse():
    global minLoad
    remainChickenHouse = list(combinations(chickenHouse, M))
    for c in remainChickenHouse:
        copyGraph = copy.deepcopy(graph)
        for i in range(N):
            for j in range(N):
                if copyGraph[i][j] == 2 and [i, j] not in c:
                    copyGraph[i][j] = 0

        minLoad = min(minLoad, chkDistance(copyGraph, house))

    return minLoad

if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = []; house = []; chickenHouse = []; chickenCnt=0
    for r in range(N):
        temp = list(map(int, input().split()))
        graph.append(temp)
        for c in range(N):
            if temp[c] == 1:
                house.append([r, c])
            if temp[c] == 2:
                chickenCnt+=1
                chickenHouse.append([r, c])
    minLoad = float("inf")
    removeChickenHouse()
    print(minLoad)