[구현/백준] 15686번 : 치킨 배달

- 문제 : https://www.acmicpc.net/problem/15686

 

문제 이해 

- 처음에 보고 bfs로 풀어야 하나 싶었는데, 탐색이 아니고 문제를 잘 이해하고 브루트 포스로 구현하면 되는 문제다. 

- 문제를 이해한 바로는 다음과 같다. 

    - 주어진 행렬의 값 중 1인 값을 house로, 2인 값을 chicken 배열에 저장한다. 

    - 문제에서 현재 존재하는 치킨집(행렬 값 2) 중에 임의로 m개를 뽑는다고 했으므로 combinations으로 chicken 좌표 중에 임의의 m개를 뽑는다. 

    - 임의로 뽑은 m개의 치킨집 각각의 좌표에 대해 각 집과의 최소 거리의 합을 구한다. m개의 치킨집 후보가 여러개 있으므로 각각마다의 치킨거리(집 ~ 치킨집 최소거리) 합의 최솟값을 구하면 그게 정답이다. 

- 주의할 점 

    - 주의해야할 거는 행렬은 n x n 크기의 행렬이고, m은 앞으로 선택한 치킨집의 개수이다. 처음에 행렬 크기를 n x m 으로 했다가 틀렸다! (house와 chicken 배열에 값을 원래 개수와 다르게 추가할 가능성이 있기 때문)

 

 

정답 풀이1 

내가 푼 풀이

from itertools import combinations

n, m = map(int, input().split())

chicken = []
house = []
for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 2:
            chicken.append([i, j])
        if temp[j] == 1:
            house.append([i, j])

answer = 1e9
candidates = list(combinations(chicken, m))
for candidate in candidates:
    count = 0
    for x, y in house:
        temp = 1e9
        for i, j in candidate:
            temp = min(temp, abs(x - i) + abs(y - j))
        count += temp
    answer = min(answer, count)
        
print(answer)

 

정답 풀이2

각 치킨 거리를 구하는 것만 함수로 빼는 풀이가 있었는데 시간이 차이가 꽤 많이 난다. 뭔가 함수로 빼고 말고가 시간복잡도에 영향을 주는게 있는걸까..??

 

def get_sum(candidate):
    count = 0
    for x, y in house:
        temp = 1e9
        for i, j in candidate:
            temp = min(temp, abs(x - i) + abs(y - j))
        count += temp 
    return count

치킨집의 위치를 임의로 m개를 구한 candidate와 house를 반복문 돌리면서 각각의 최소 거리 합을 구하는 로직이다.

 

from itertools import combinations

n, m = map(int, input().split())

chicken = []
house = []
for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 2:
            chicken.append([i, j])
        if temp[j] == 1:
            house.append([i, j])

def get_sum(candidate):
    count = 0
    for x, y in house:
        temp = 1e9
        for i, j in candidate:
            temp = min(temp, abs(x - i) + abs(y - j))
        count += temp 
    return count 

answer = 1e9
candidates = list(combinations(chicken, m))
for candidate in candidates:
    answer = min(answer, get_sum(candidate))
        
print(answer)