[백준] 15686번 치킨 배달 (python)

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

정답 코드는 맨 밑에 있습니다!

---

 

• 음 그래프네. BFS로 풀면 되나?
• 근데 집집마다 치킨 거리가 다르네...
• 게다가 어떤 치킨집을 없애느냐에 따라 나뉘네...
• 가까운 치킨 집을 지울 때가 정답일 때도 있네..?
• 심지어 M이 13 이하네..?
• 이건 완탐이다...

라는 의식의 흐름으로 문제를 풀려고 했다. 근데 잘 안 풀린다..

 

 

처음 풀었을 때 틀린 코드

 

 

두 번 풀었을 때 틀린 코드

import sys
from collections import defaultdict
input = sys.stdin.readline

def find_neareat_distance(houses, chicken_houses):
    answer = 0

    for house in houses:
        nearest = 1e9

        for chicken_house in chicken_houses:
            nr = abs(house[0] - chicken_house[0][0])
            nc = abs(house[1] - chicken_house[0][1])
            distance = nr + nc

            if nearest > distance:
                nearest = distance

        answer += nearest
    return answer


def find_chicken_distance():
    nearest_chicken = defaultdict(int)
    selected = [0, 0]
    
    for chicken_house in chicken_houses:
        nearest = 1e9
        distance = 0

        for house in houses:
            nr = abs(house[0] - chicken_house[0])
            nc = abs(house[1] - chicken_house[1])
            distance += (nr + nc)
        if nearest >= distance:
            nearest = distance
            selected = chicken_house
                
        nearest_chicken[(selected[0], selected[1])] += distance
    sorted_chicken = sorted(nearest_chicken.items(), key=lambda x: x[1])
    return sorted_chicken

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
houses = []
chicken_houses = []
chicken_distances = []
distances = defaultdict(int)

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            houses.append([i+1, j+1])

for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            chicken_houses.append([i+1, j+1])

nearest_chicken_houses = find_chicken_distance()
print(find_neareat_distance(houses, nearest_chicken_houses[:m]))

 

위 풀이는 대부분의 테케를 맞혀서 정답이라 생각했는데 아니었다. 반례는 아래에 있다.

 

위 반례는 통과하는데, 아래 반례는 통과하지 못한다... 왜냐하면 내 코드는 가운데에 있는 치킨집을 포함하기 때문이다... 이 예제로 내가 어떤 부분을 잘못 구현했는지 알 수 있었다.

 

다시 구현 과정을 정리하자면

1. 모든 치킨집 위치를 기록한다.
2. 치킨집을 M씩 슬라이싱하여 치킨 거리를 기록한다. (M개의 치킨집씩 탐색)
3. 그중 최소가 되는 경우를 출력한다.

M이 13 이하이기 때문에 가능한 방식이다. 아직 못 풀었기 때문에 다시 풀러 가야 된다...

오늘 무조건 풀 거다.. 풀고 와서 다시 복기할 예정...

 

---

 

이 글을 쓴 지 20분 만에 풀었다! 역시 알고리즘은 원인을 찾고 직접 쓰면서 풀어나가는 게 도움이 많이 된다.

 

문제를 틀린 이유

• 대칭 중앙에 있는 치킨집을 무조건 끼는 게 가장 좋은 치킨 거리인 줄 알았지만 아니었다.
• 그래서 그냥 다 구했다. M개의 치킨집으로 슬라이싱 한 후 모두 탐색해 주었다. (이때 python 조합 라이브러리를 사용했다.)

 

정답 코드

import sys
from itertools import combinations
from collections import defaultdict
input = sys.stdin.readline

def calculate_distance(chickens):
    total_distance = 0

    for house in houses:
        min_distance = 1e9

        for chicken in chickens:
            chicken_x, chicken_y = chicken[0], chicken[1]
            house_x, house_y = house[0], house[1]
            distance = abs(chicken_x - house_x) + abs(chicken_y - house_y)
            
            if min_distance > distance:
                min_distance = distance

        total_distance += min_distance
    return total_distance


n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
houses = []
chicken_houses = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            houses.append([i+1, j+1])

for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            chicken_houses.append([i+1, j+1])

min_distance = 1e9
for chickens in combinations(chicken_houses, m):
    distance = calculate_distance(chickens)
    if min_distance > distance:
        min_distance = distance
print(min_distance)