백준 15686 치킨 배달(with Python)

내가 생각한 Solution

문제에서 생각해볼 점

• 처음에 빠른 길찾기의 목적 때문에 BFS로 접근하여 시간 초과가 발생했습니다.

• 하지만 이 문제는 벽이 있거나 하는 상황이 아니기 때문에 두 좌표의 거리 값 계산으로만 빠른 길 찾기가 가능합니다.

  • 이 부분만 유의하시면 정말 쉬운 문제입니다.

코드 구현

잘못 생각한 코드 (BFS 접근, 시간 초과 발생)

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy

def find_chicken_path(q):
    chicken_path = 0
    while q:
        chicken_path += 1
        for i in range(len(q)):
            r, c = q.popleft()
            for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                if 0 <= r + dr < N and 0 <= c + dc < N:
                    if brd_copy[r + dr][c + dc] != 3:
                        if brd_copy[r + dr][c + dc] == 2:
                            return chicken_path
                        brd_copy[r + dr][c + dc] = 3
                        q.append([r + dr, c + dc])

N, M = map(int, sys.stdin.readline().split())

brd = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

houses = []
chicken_houses = []
for r in range(N):
    for c in range(N):
        if brd[r][c] == 2:
            chicken_houses.append([r, c])
            brd[r][c] = 0
        elif brd[r][c] == 1:
            houses.append([r, c])

result = 1e+30
for selected_chicken_houses in combinations(chicken_houses, M):

    chicken_paths = []
    for house in houses:
        brd_copy = deepcopy(brd)

        for chicken_house_r, chicken_house_c in selected_chicken_houses:
            brd_copy[chicken_house_r][chicken_house_c] = 2

        queue = deque([house])
        brd_copy[house[0]][house[1]] = 3

        chicken_paths.append(find_chicken_path(queue))

    sum_chicken_paths = sum(chicken_paths)
    if sum_chicken_paths < result:
        result = sum_chicken_paths

print(result)

정답 코드

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy

N, M = map(int, sys.stdin.readline().split())

brd = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

houses = []
chicken_houses = []
for r in range(N):
    for c in range(N):
        if brd[r][c] == 2:
            chicken_houses.append([r, c])
            brd[r][c] = 0
        elif brd[r][c] == 1:
            houses.append([r, c])

result = 1e+30
for selected_chicken_houses in combinations(chicken_houses, M):

    tmp_result = 0
    for house_r, house_c in houses:
        tmp_min_path = 10000000
        for chicken_house_r, chicken_house_c in selected_chicken_houses:
            tmp_path = abs(house_r - chicken_house_r) + abs(house_c - chicken_house_c)
            if tmp_path < tmp_min_path:
                tmp_min_path = tmp_path

        tmp_result += tmp_min_path

    if tmp_result < result:
        result = tmp_result

print(result)