15686번 못 푼 문제 - 2024.01.26

15686번 - 치킨 배달

from collections import deque
import sys
import copy

input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y):
    visited[x][y] = 1
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=N:
                continue 
            if not visited[nx][ny]:
                if graph[nx][ny] == 2:
                    return graph[x][y]                    
                if graph[nx][ny] >= 0:
                    graph[nx][ny] = graph[x][y] + 1
                    visited[nx][ny] = 1
                    que.append([nx,ny])

N,M = map(int,input().split())
graph = []
visited = [[0]*N for _ in range(N)]
distance = 0
que = deque()
for _ in range(N):
    a = list(map(int,input().split()))
    graph.append(a)
graph_copy = copy.deepcopy(graph)


#살려둘 치킨집을 구하는 경우의 수 
def combination(chicken):
    if len(tmp) == M:
        chicken_choice.append(tmp[:])
        return 
    else:
        for i in range(len(chicken)):
            if visited_chicken[i]:
                continue
            tmp.append(chicken[i])
            visited_chicken[i] = 1
            combination(chicken)
            tmp.pop()
            visited_chicken[i] = 0

tmp = []
chicken = []
chicken_choice = []
for p in range(N):
    for q in range(N):
        if graph[p][q] == 2:
            chicken.append([p,q])
visited_chicken = [0]*len(chicken)

combination(chicken)

distance = 0
ans = []


#치킨거리 구하기 
while chicken_choice:
    choice = chicken_choice.pop()
    for m in range(N):
        for o in range(N):
            if graph[m][o] == 2:
                graph[m][o] = 0
    while choice:
        [x,y] = choice.pop()
        graph[x][y] = 2
    graph_copy2 = copy.deepcopy(graph)

    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                distance += bfs(i,j)
                visited = [[0]*N for _ in range(N)]
                graph = copy.deepcopy(graph_copy2)
                que.clear()                
    ans.append(distance)
    distance = 0
    graph = copy.deepcopy(graph_copy)

print(min(ans))

BFS와 Combination으로 시도하였으나 시간초과 및 메모리 제한으로 실패.
이어서 BFS를 제외한 순수한 점대점 거리로 계산하였으나 역시 실패.