[BOJ] 치킨 배달 (G5, 15686) - 잃어버린 3시간

 

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

 

다 해놓고 얼탱이 없는 미스로 3시간을 날렸다. dfs 돌릴 때 돌아갈 다음 칸을 잘못 설정하였다... 얼탱이 없는 오타...

dfs(pick_num + 1, i + 1) 해야 한다는걸 dfs(pick_num+1, cur_pos+1) 해버림....

그 외에는 G5치고는 쉬운 그냥 dfs.

잃어버린 나의 3시간....

import sys
input = sys.stdin.readline
def chick_dist(chick_list, house_list):
    global min_length
    sum_dist = 0
    for cur_h in house_list:
        cur_min_dist = sys.maxsize
        for i in range(len(chick_list)):
            if visited[i]:
                cur_dist = abs(cur_h[0] - chick_list[i][0]) + abs(cur_h[1] - chick_list[i][1])
                if cur_dist < cur_min_dist:
                    cur_min_dist = cur_dist
        sum_dist += cur_min_dist
    if sum_dist < min_length:
        min_length = sum_dist

def dfs(pick_num, cur_pos):
    global min_length
    if pick_num <= chick_cut:
        chick_dist(chick_list, house_list)
    elif pick_num > chick_cut:
        pass
    for i in range(cur_pos, len(chick_list)):
        if not visited[i]:
            visited[i] = True
            # 여기 실수 하지 마!!! 현재 온 만큼 가야 하는데! 뭐한거!!!
            dfs(pick_num + 1, i + 1)
            visited[i] = False
    
N, chick_cut = map(int, input().split())
maps = []
house_list = []
chick_list = []

for i in range(N):
    cur_row = list(map(int, input().split()))
    for j in range(N):
        if cur_row[j] == 1:
            house_list.append([i, j])
        elif cur_row[j] == 2:
            chick_list.append([i, j])
    maps.append(cur_row)
    
visited = [False] * len(chick_list)
min_length = sys.maxsize
dfs(0, 0) # 고른 개수, 현재 치킨집 체크
print(min_length)

사실, 그리디하게 M개 다 쓸때만 최소거리이긴 할거 같고, 실제로 맞았습니다! 나오지만 있는 그대로 구현한 코드도 통과된다...