[구현] 치킨배달

치킨배달

from itertools import combinations
from collections import deque

n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y, notlst, type):
    visited[x][y] = True
    queue = deque([(x,y)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>(n-1) or ny<0 or ny>(n-1):
                continue
            if type==1: # 원래 위치
                if visited[nx][ny] == False and grid[nx][ny] == 2:
                    return (nx, ny)
            if type==2:
                if visited[nx][ny] == False and grid[nx][ny] == 2 and (nx, ny) in notlst:
                    return (nx, ny)
            visited[nx][ny] = True
            queue.append((nx, ny))


# lst_1 = [] # 1인 좌표 리스트
lst_2 = [] # 2인 좌표 리스트
cls_pair = {} # 1과 가장 가까운 2인 좌표
for i in range(n):
    for j in range(n):
        if grid[i][j] == 2:
            lst_2.append((i,j))
        elif grid[i][j] == 1:
            visited = [[False for _ in range(n)] for _ in range(n)]
            # lst_1.append((i, j))
            cls_pair[(i,j)] = bfs(i, j, None, 1)

comb = list(combinations(lst_2, m))

dis_lst = []
for g in comb: # 치킨집 조합
    all_distance = 0
    # for i in lst_1: # 각 치킨집 조합의 치킨거리총합 계산
    for x in range(n):
        for y in range(n):
            if grid[x][y] == 1:
                if cls_pair[(x,y)] in g:
                    a, b = cls_pair[(x,y)]
                else:
                    visited = [[False for _ in range(n)] for _ in range(n)]
                    a, b = bfs(x, y, g, 2) # 가장 가까운 치킨집 좌표
                all_distance += abs(x-a)+abs(y-b)
    dis_lst.append(all_distance)

print(min(dis_lst))

• 메모리 초과, 시간 초과를 해결하기 위해 여러 시도
• bfs로 가장 가까운 치킨집을 찾는 대신 그냥 모든 치킨집과의 거리를 재보면 된다. 치킨집은 최대 13개이므로!!

from itertools import combinations

n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

lst_1 = [] # 1인 좌표 리스트
lst_2 = [] # 2인 좌표 리스트
for i in range(n):
    for j in range(n):
        if grid[i][j] == 2:
            lst_2.append((i,j))
        elif grid[i][j] == 1:
            lst_1.append((i, j))

comb = list(combinations(lst_2, m))

dis_lst = []
for g in comb: # 치킨집 조합
    all_distance = 0
    for h in lst_1:
        dis = []
        x, y = h
        for ch in g:
            a, b = ch
            dis.append(abs(x-a)+abs(y-b))
        all_distance += min(dis)
    dis_lst.append(all_distance)

print(min(dis_lst))

얻은 교훈

• 문제의 범위를 생각하고 부르트포스가 시간이 적게 걸릴 수도 있다는 생각을 해보기