728x90
*문제 출처는 삼성전자, 코드트리에 있습니다.
삼멘 4일차
문제 제목: 병원 거리 최소화하기
나의 풀이
처음 BFS, 조합 구현 코드에서 메모리 초과가 났었음
이유: 조합 코드에서 리스트를 저장하는 과정에서 초과
해결: 조합을 저장하지 않고 만든 즉시 병원과 사람들간 거리 최소 구함
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
person = [] # 사람 위치
hospital = [] # 병원 위치
# 사람들 위치와 병원 위치 저장
for i in range(n):
for j in range(n):
if maps[i][j] == 1:
person.append((i, j))
elif maps[i][j] == 2:
hospital.append((i, j))
answer = 1e5 # 최소 거리 합을 저장할 변수
# 조합을 생성하면서 바로 처리하는 재귀 함수
def combination(num, arr, start):
global answer
if len(arr) == num:
# 조합이 완성되면 거리 계산
total_dist = 0
for px, py in person:
p_dist = 1e5
for cx, cy in arr:
dist = abs(px - cx) + abs(py - cy)
p_dist = min(p_dist, dist)
total_dist += p_dist
answer = min(answer, total_dist)
return
for i in range(start, len(hospital)):
combination(num, arr + [hospital[i]], i + 1)
# m개의 병원을 선택하는 조합 만들기
combination(m, [], 0)
print(answer)
※ 알아야 할 것
- 메모리 초과나면 리스트에 조합 저장하지않고 바로 답구하기
728x90