[백준 15868번] 치킨 배달 - python

문제 링크

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

15686번: 치킨 배달

풀이

- bfs와 조합 사용해서 풀었는데 시간초과 

# bfs 사용한 시간 초과 코드 
from collections import deque
from itertools import combinations 
import copy 
import sys
input = sys.stdin.readline 

dx = [ 1, -1, 0, 0 ]
dy = [ 0, 0, 1, -1 ]

# 집과 치킨 집까지의 최단 거리 반환 
def bfs(tmp, a, b):
  visited = [ [False] * n for _ in range(n)]
  q = deque()
  q.append((a,b,0))
  visited[a][b] = True

  while q :
    x, y, cnt = q.popleft()

    if tmp[x][y] == 2 :
      return cnt 
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] :
        q.append((nx,ny, cnt +1))
        visited[nx][ny] = True

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

graph = []

for _ in range(n):
  graph.append(list(map(int,input().split())))

# 치킨의 위치 저장 
chick = []
for i in range(n):
  for j in range(n):
    if graph[i][j] == 2:
      chick.append((i,j))

# 폐점시킬 치킨집 선택 
combine = list(combinations(chick,len(chick)-m))
answer = int(1e9)

for i in combine :
    tmp = copy.deepcopy(graph)
    # 폐점 시킨 치킨집 0 으로 만들기 
    for j in i:
      tmp[j[0]][j[1]] = 0
    
    result = 0 
    # 집일 경우 가까운 치킨 집까지의 최단 거리 result에 더하기 
    for a in range(n):
      for b in range(n):
        if tmp[a][b] == 1 :
          result += bfs(tmp,a,b)
    # 치킨 거리 최솟값으로 갱신 
    if result < answer :
      answer = result 
      
print(answer)

- home에 집 위치를 저장하고, 고를 치킨집들에 대하여 집과 치킨집 사이의 최단 거리를 구하여 최솟값을 찾아주는 브루트포스로 풀이 

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

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

graph = []

for _ in range(n):
  graph.append(list(map(int,input().split())))

# 치킨집 위치 저장
chick = []
# 집 위치 저장 
home = []
for i in range(n):
  for j in range(n):
    if graph[i][j] == 2:
      chick.append((i,j))
    if graph[i][j] == 1 :
      home.append((i,j))
      
# 폐점시키지 않을 치킨 집 구하기 
combine = list(combinations(chick, m))
answer = int(1e9)

for i in combine :
  result = 0 
  # 집과 폐점 시키지 않은 치킨집 사이의 거리 중 최단 거리 result에 더하기 
  for b in home :
    tmp = int(1e9)
    for a in i :
      tmp = min(tmp, abs(b[0]-a[0]) + abs(b[1]-a[1]))
    result += tmp 
  # 치킨 거리 최솟값 갱신 
  if result < answer :
    answer = result 
      
print(answer)