백준 15686 [치킨배달] 파이썬

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

15686번: 치킨 배달

# 백준 15686 치킨배달
from itertools import combinations
from collections import deque
import sys
input = sys.stdin.readline
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
N, M = map(int, input().split())
field = []
cHouses = []
clients = []
for i in range(N):
    s = list(map(int, input().split()))
    for j in range(N):
        if s[j] == 2:
            cHouses.append([i, j])
        elif s[j] == 1:
            clients.append([i, j])
    field.append(list(map(int, s)))


def bfs(combi):
    q = deque([])
    for client in clients:
        r, c = client
        field_[r][c] = 1
    for cHouse in combi:
        r, c = cHouse
        field_[r][c] = 2
        visited[r][c] = 0
        q.append([r, c])
    dist = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            R = r+dr[i]
            C = c+dc[i]
            if 0 <= R < N and 0 <= C < N and visited[R][C] == 0 and [R, C] not in combi:
                visited[R][C] = visited[r][c]+1
                q.append([R, C])
                if field_[R][C] == 1:
                    dist += visited[R][C]
    return dist


lst = []
combination = combinations(cHouses, M)
for combi in combination:
    visited = [[0]*N for _ in range(N)]
    field_ = [[0]*N for _ in range(N)]
    lst.append(bfs(combi))
print(min(lst))

(pypy3로 통과하였습니다..)

 

# 치킨배달 python3 통과
import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(n))
result = 999999
house = []      # 집의 좌표
chick = []      # 치킨집의 좌표

for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append([i, j])
        elif city[i][j] == 2:
            chick.append([i, j])

for chi in combinations(chick, m):  # m개의 치킨집 선택
    temp = 0            # 도시의 치킨 거리
    for h in house: 
        chi_len = 999   # 각 집마다 치킨 거리
        for j in range(m):
            chi_len = min(chi_len, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
        temp += chi_len
    result = min(result, temp)

print(result)

python3로는 어떻게 시간초과가 안나고 해결했을까...? 라는 궁금증이 생겨 다른 분의 코드를 참고하여 올린다.

복잡하게 bfs로 해결 할 필요없이 그냥 모든 경우에 대해서 직접 구해주는 것이다.

( 때로는 바로 부딪혀 보는 것도 좋은 방법인것 같다!)

 

https://codesyun.tistory.com/185 참조 블로그이다.