삼성 SW역량테스트 기출 / 2018 상반기 오후 2번 문제 병원 거리 최소화하기 - 조합 / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 4일차

문제 제목: 병원 거리 최소화하기

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/min-of-hospital-distance/submissions?page=1&pageSize=20&tier=11%2C11

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

나의 풀이

 

처음 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)

 

---

※ 알아야 할 것

- 메모리 초과나면 리스트에 조합 저장하지않고 바로 답구하기