문제
https://www.acmicpc.net/problem/15686
풀이
최단거리를 구해야해서 처음에 BFS를 생각했다. 근데 시간복잡도를 계산해보니 너무 높게 나와서 문제를 다시 읽어봤는데, 집의 개수와 치킨집의 개수가 제한이 되어있어서 BFS가 아닌 그냥 주어진 애들끼리 2중for문으로 일일이 비교하면 시간복잡도가 많이 줄어들었다.
문제에서 수의 최대값 제한 조건을 자세히 살피자. 이걸 통해 풀이방향을 뽑아낼 수 있다.
- 변수명 확실히 신경써서 지으니까 코드적을때나 전체 쭉 살필때 훨씬 편하다.
itertools쓰지 않고 경우의 수(순열, 조합) 뽑는 것도 연습하자.(ex. N과 M 문제 시리즈)
from itertools import combinations
EMPTY, HOUSE, BBQ = 0, 1, 2
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
def get_distance(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)
all_house_list = []
all_bbq_list = []
for i in range(N):
for j in range(N):
if graph[i][j] == HOUSE:
all_house_list.append((i, j))
elif graph[i][j] == BBQ:
all_bbq_list.append((i, j))
ans = float('inf')
for bbq_list in combinations(all_bbq_list, M):
now_total_distance = 0
for hx, hy in all_house_list:
now_total_distance += min(
get_distance(hx, hy, bx, by) for bx, by in bbq_list)
ans = min(ans, now_total_distance)
print(ans)
성장!