[알고리즘] BOJ 15686번 제출 코드 회고(Python)

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

15686번: 치킨 배달

 

문제를 요약하자면 'M개의 치킨집을 뽑아 모든 집에서 각각의 최소 치킨 거리에 맞는 치킨집을 찾아 최소 치킨 거리의 합을 구하라'는 문제였다.

문제를 보고 'DFS와 백트래킹을 이용하여 풀면 되겠다'라고 생각을했고 해당 개념의 알고리즘 문제를 푼 지 오래됐지만 호기롭게 도전해보았다.

 

 

<제출코드>

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

houses = []
chickens = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            houses.append((i, j))
        if graph[i][j] == 2:
            chickens.append((i, j))

selected_chickens = []
ans = sys.maxsize


def dfs():
    global ans

    if len(selected_chickens) == M:
        total_distance = 0
        for house in houses:
            min_chicken_distance = sys.maxsize
            for selected_chicken in selected_chickens:
                chicken_distance = abs(house[0] - selected_chicken[0]) + abs(
                    house[1] - selected_chicken[1]
                )
                min_chicken_distance = min(min_chicken_distance, chicken_distance)
            total_distance += min_chicken_distance

        ans = min(ans, total_distance)
        return

    for chicken in chickens:
        if chicken not in selected_chickens:
            selected_chickens.append(chicken)
            dfs()
            selected_chickens.pop()


dfs()
print(ans)

selected_chickens라는 배열에다가 거리를 구하기 위해 선택된 치킨집을 넣어주고 모든 각각의 집에서 selected_chickens배열의 치킨집들과의 최소 거리를 구하기 위해 for문을 돌려주는 식으로 구현을 해주었다.

모든 예제 test case를 통과하고 '오.. 아직 까먹진 않았구나'하고 제출 버튼을 눌렀지만

 

 

ㅠㅠ 시간 초과가 떠버렸다....

 

왜 그럴까 곰곰히 생각을 해보았다.

   for chicken in chickens:
        if chicken not in selected_chickens:
            selected_chickens.append(chicken)
            dfs()
            selected_chickens.pop()

dfs함수내의 위의 코드는 모든 치킨 집에 대해 중복 검사(if chicken not in selected_chickens 부분)를 수행하고 있다.
이 방식은 선택된 치킨 집의 배열(selected_chickens)에 현재 치킨 집이 포함되어 있는지를 매번 확인하는데 이로 인해, 각 단계에서 모든 치킨 집을 순회하면서 중복을 확인하게 되어 비효율적이게 된다.

중복 확인 과정이 리스트에 대한 in 연산을 사용하기 때문에, 선택된 치킨 집의 수가 많아질수록 시간 복잡도도 O(N*M)이 된다.

 

<재제출 코드>

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

houses = []
chickens = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            houses.append((i, j))
        if graph[i][j] == 2:
            chickens.append((i, j))

selected_chickens = []
ans = sys.maxsize


def dfs(start):
    global ans

    if len(selected_chickens) == M:
        total_distance = 0
        for house in houses:
            min_chicken_distance = sys.maxsize
            for selected_chicken in selected_chickens:
                chicken_distance = abs(house[0] - selected_chicken[0]) + abs(
                    house[1] - selected_chicken[1]
                )
                min_chicken_distance = min(min_chicken_distance, chicken_distance)
            total_distance += min_chicken_distance

        ans = min(ans, total_distance)
        return

    for i in range(start, len(chickens)):
        selected_chickens.append(chickens[i])
        dfs(i + 1)
        selected_chickens.pop()


dfs(0)
print(ans)

달라진 부분은 dfs함수를 재귀적으로 호출하는 방식이 달라졌다.

start 매개변수를 사용하여 재귀적으로 dfs를 호출하며, 각 단계에서 start 인덱스 이후의 치킨 집만을 고려했다.
이 방식은 중복을 매우 효율적으로 제거하며, 각 치킨 집을 정확히 한 번씩만 고려하도록 했고 이로 인해 알고리즘의 시간 복잡도 또한 전체 치킨집 개수가 C라면 그 중 중복없이 M개를 뽑는 것이므로 O(N*M)보다는 현저히 작다.

 

 

물론 더 빠르게 처리가 되도록 코드를 작성하신 분들도 많이 계시고 내 코드를 더 최적화 시킬수있겠지만 지금의 내 수준에서 만약 코딩테스트에 이런 비슷한 문제가 나온다면 최적화된 코드를 바로 떠올리고 작성할 자신이 없다... ㅠㅠ

후... 아직 많이 부족하다