15686: 치킨 배달

• 치킨 거리를 구하는 공식이 그냥 abs(home[0] - chicken[0]) + abs(home[1] - chicken[1]) 이어서 생각보다 간단했던 백트래킹 문제

dfs()

• 종료조건: depth (선택한 치킨 집의 개수)가 M이 될 때, 최소거리를 구하고 global_distance를 갱신해준 후 return
• dfs 진행: chicken 리스트를 순회하며, now_chicken 리스트에 chicken[i]가 없는 경우 now_chicken 리스트에 chicken[i]을 append 해주고 dfs 진행 (dfs진행 코드 아랫줄에 backtracking을 위해 now_chicken.pop() 해줘야 함)

시간 초과 난 코드

import sys

def dfs(depth):
    global global_distance

    if depth == M:
        total_distance = 0
        for i in range(len(home)):
            distance = int(1e9)
            for j in range(len(now_chicken)):
                distance = min(distance, abs(home[i][0] - now_chicken[j][0]) + abs(home[i][1] - now_chicken[j][1]))
            total_distance += distance
        global_distance = min(global_distance, total_distance)
        return

    for chick in chicken:
        if chick not in now_chicken:
            now_chicken.append(chick)
            dfs(depth+1)
            now_chicken.pop()

N, M = map(int, sys.stdin.readline()[:-1].split())
home = []
chicken = []
for i in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    for j in range(N):
        if tmp[j] == 1:
            home.append([i, j])
        if tmp[j] == 2:
            chicken.append([i, j])

global_distance = int(1e9)
now_chicken = []
dfs(0)
print(global_distance)

• 아래 출력 결과처럼 now_chicken 리스트가 중복되는 경우를 제거해줘야 시간초과가 발생하지 않음
  

최종 코드

import sys

def dfs(depth, index_flag):
    global global_distance

    if depth == M:
        #print(now_chicken)
        total_distance = 0
        for i in range(len(home)):
            distance = int(1e9)
            for j in range(len(now_chicken)):
                distance = min(distance, abs(home[i][0] - now_chicken[j][0]) + abs(home[i][1] - now_chicken[j][1]))
            total_distance += distance
        global_distance = min(global_distance, total_distance)
        return

    for i in range(index_flag, len(chicken)):
        chick = chicken[i]
        if chick not in now_chicken:
            now_chicken.append(chick)
            dfs(depth + 1, i + 1)
            now_chicken.pop()

N, M = map(int, sys.stdin.readline()[:-1].split())
home = []
chicken = []
for i in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    for j in range(N):
        if tmp[j] == 1:
            home.append([i, j])
        if tmp[j] == 2:
            chicken.append([i, j])

global_distance = int(1e9)
now_chicken = []; visit = [[0 for _ in range(N)] for __ in range(N)]
dfs(0, 0)
print(global_distance)

• dfs 함수의 input parameter에 index_flag 변수를 추가하여, dfs를 진행할 때 이전 depth의 치킨 집 이후의 치킨 집들부터 dfs를 순회하도록 추가 구현해줌 -> 중복되는 경우 제거 & 시간 단축