Baekjoon 15686번 치킨 배달

문제

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

걸린 시간

02 : 24 : 37

풀이

Python3

from itertools import combinations

def distance(house, chicken):
    r1, c1 = house 
    last = 98
    for loc in chicken:
        r2, c2 = loc
        value = abs(r1-r2)+abs(c1-c2)
        if last >= value:
            last = value
    return last

if __name__ == "__main__":
    # M : 남길 치킨집의 개수
    N, M = map(int, input().split())

    city = []
    house = []
    chicken = []
    survive = []    

    for i in range(1, N+1):
        row = list(map(int, input().split()))
        city.append(row)
        for j in range(1, N+1):
            if row[j-1] == 1:
                house.append([i, j])
            elif row[j-1] == 2:
                chicken.append([i, j])

    # 폐업당하지 않은 치킨집의 수 만큼 부분집합 생성
    subset = combinations(chicken, M)
    survive.extend(subset)

    result = 98*2*50
    if len(survive):
        for s in survive:
            road = 0
            for i in range(0, len(house)):
                road += distance(house[i], s)
            if result >= road:
                result = road
    else:
        for i in range(0, len(house)):
            road += distance(house[i], chicken)
        result = road

    print(result)

문제에서 알려준 집과 치킨집 사이의 거리를 좌표로 구하는 방법을 무시하고 BFS 로 구하려다 시간초과가 났다.

M(폐업시키지 않을 치킨집의 수)개 쌍으로 이루어진 치킨집의 부분집합을 구하고 집과의 거리를 모두 조사하면 되는 문제인데 BFS 를 사용하려고 하다보니 반대로 폐업시킬 치킨집의 부분집합을 구하여 집과의 거리를 계산했다.

문제에서 주어진 조건이나 방법은 절대로 괜히 준 정보가 아니라는걸 항상 잊지 말아야겠다.

어떻게 만들어야할 지 몰라 한참을 고민했던 부분집합은 itertools 의 combinations 메소드를 이용하면 쉽게 만들 수 있었다.

참고

• [python] set 자료형 활용하여 부분집합 구하기 / 부분집합인지 확인하는 방법