파이썬으로 풀어보는 백준 15686번 치킨 배달 (삼성 A형 기출 문제)

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

15686번: 치킨 배달

 

내 풀이:

def BFS(ch):
    global result
    lst = [200] * len(house)
    for i in range(len(house)):
        for j in range(len(ch)):
            value = abs(house[i][0] - ch[j][0]) + abs(house[i][1] - ch[j][1])
            if value < lst[i]:
                lst[i] = value
 
    result.append(sum(lst))
    return
 
 
def select_chicken(lst, idx):
    global M
    if len(lst) == M:
        BFS(lst)
        return
 
    elif len(lst) + len(chicken_init) - idx < M:
        return
 
    select_chicken(lst, idx + 1)
    lst.append(chicken_init[idx])
    select_chicken(lst, idx+1)
    lst.pop(-1)
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]
result = []
 
chicken_init = []
house = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            chicken_init.append([i, j])
        elif arr[i][j] == 1:
            house.append([i, j])
select_chicken([], 0)
 
print(min(result))

Python3, 시간 초과

문제를 처음 봤을 때는 '최단거리 or 최단시간문제는 BFS'라는 고정관념 때문에 BFS로 접근하여 문제를 풀었다가 시간 초과에 걸렸다. 전체 arr는 단 한 번만 탐색하기 때문에 다른 최악의 경우의 수를 확인하면 집은 최대 100개이며 남길 치킨집의 경우의 수는 13 C 6으로 최대 1716이다. 하나의 집에 대해서 가장 가까운 치킨집을 BFS로 탐색하기 때문에 100번의 BFS 함수를 돌린다.

 

 

def BFS(ch):
    global result
    lst = [200] * len(house)
    for i in range(len(house)):
        for j in range(len(ch)):
            value = abs(house[i][0] - ch[j][0]) + abs(house[i][1] - ch[j][1])
            if value < lst[i]:
                lst[i] = value
 
    result.append(sum(lst))
    return
 
 
def select_chicken(lst, idx):
    global M
    if len(lst) == M:
        BFS(lst)
        return
 
    elif len(lst) + len(chicken_init) - idx < M:
        return
 
    select_chicken(lst, idx + 1)
    lst.append(chicken_init[idx])
    select_chicken(lst, idx+1)
    lst.pop(-1)
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]
result = []
 
chicken_init = []
house = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            chicken_init.append([i, j])
        elif arr[i][j] == 1:
            house.append([i, j])
select_chicken([], 0)
 
print(min(result))

Python3, 560ms

치킨 거리를 구할 때 각 집 별 치킨집까지의 거리들 중 가장 짧은 것만 저장하고 그 리스트의 sum값을 result 리스트에 append하여 min(result) 값을 출력하였다. 문제에 대한 코드 기본 틀은 1시간 체 걸리지 않았으나 BFS라는 잘못된 방향 설정으로 1시간 10분 만에 제출하였다. 문제 나이도에 비해 시간을 오래 들인 것 같아 문제 풀이 방향 설정에 대한 신중함이 필요할 것 같다.