순열과 조합 - BOJ : 15686 치킨 배달

문제로 바로가기

크기가 m인 치킨 집 조합들의 도시 치킨 거리를 구해서 minimum을 찾아주면 된다. 조합을 구현하는 데에 시간이 오래 걸렸다. 그냥 라이브러리 써주는 게 편하다.

순열 조합 라이브러리

from itertools import permutations
list(permutation(iter.., size))

from itertools import combinations
list(combinations(iter.., size))

조합 직접 구현한 문제 풀이

import sys
from collections import deque
input = sys.stdin.readline


# 집 하나의 치킨 거리를 계산하기
def cDistance(chick, h):
    min_d = getDis(chick[0], h)
    for i in range(1, len(chick)):
        if min_d > getDis(chick[i], h):
            min_d = getDis(chick[i], h)
    return min_d

def getDis(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# 치킨거리는 집과 가장 가까운 치킨집 사이의 거리
# 도시의 치킨거리는 모든 집의 치킨 거리의 합
# 거리는 | r1 - r2 | + | c1 - c2|

# 최대 m개만 남기고 나머지 치킨집이 사라졌을 때, 도시의 치킨 거리의 최솟값

size_city, m = list(map(int, list(input().strip().split())))
ls = [list(map(int, list(input().strip().split()))) for _ in range(size_city)]

chicken = []
house = []
for i in range(size_city):
    for j in range(size_city):
        if ls[i][j] == 1:
            house.append((i, j)) # i열 j행
        elif ls[i][j] == 2:
            chicken.append((i, j))


visit = deque([i for i in range(m)])
c = []
for i in visit:
    c.append(chicken[i])
min_dist = 0
for h in house:
    min_dist += cDistance(c, h)
while visit[0] != len(chicken) - 1 :
    last = visit.pop()
    while visit and last == len(chicken) - 1:
        last = visit.pop()
    visit.append(last + 1)
    while len(visit) < m and visit[-1] + 1 < len(chicken):
        visit.append(visit[-1] + 1)
    if len(visit) == m:
        temp = 0
        c = []
        for i in visit:
            c.append(chicken[i])
        for h in house:
            temp += cDistance(c, h)
            if temp >= min_dist:
                break
        if temp < min_dist:
            min_dist = temp
print(min_dist)

조합 라이브러리 이용한 문제 풀이

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


# 집 하나의 치킨 거리를 계산하기
def cDistance(chick, h):
    min_d = getDis(chick[0], h)
    for i in range(1, len(chick)):
        if min_d > getDis(chick[i], h):
            min_d = getDis(chick[i], h)
    return min_d

def getDis(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# 치킨거리는 집과 가장 가까운 치킨집 사이의 거리
# 도시의 치킨거리는 모든 집의 치킨 거리의 합
# 거리는 | r1 - r2 | + | c1 - c2|

# 최대 m개만 남기고 나머지 치킨집이 사라졌을 때, 도시의 치킨 거리의 최솟값

size_city, m = list(map(int, list(input().strip().split())))
ls = [list(map(int, list(input().strip().split()))) for _ in range(size_city)]

chicken = []
house = []
for i in range(size_city):
    for j in range(size_city):
        if ls[i][j] == 1:
            house.append((i, j)) # i열 j행
        elif ls[i][j] == 2:
            chicken.append((i, j))

visit = deque([i for i in range(m)])
c = []
for i in visit:
    c.append(chicken[i])
min_dist = 0
for h in house:
    min_dist += cDistance(c, h)

for ls in combinations(chicken, m):
    print(ls)
    temp = 0
    for h in house:
        temp += cDistance(ls, h)
        if temp >= min_dist:
            break
    if temp < min_dist:
        min_dist = temp
print(min_dist)