잊을만하면 순열조합 연습하기 -치킨배달-

1. 문제

 

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

 

어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리라고 부르고

 

모든 집의 치킨 거리의 합이 해당 도시의 치킨 거리이다.

 

최대 m개의 치킨 집만 선택해서 가능한 도시의 치킨 거리의 최솟값은

 

 

2. 풀이

 

항상.. 문제를 잘 읽어야한다

 

"어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리"

 

이것부터 제대로 보질 못했는데.. 빨리 봐서 다행이긴해

 

조합을 구현한 재귀함수가 생각이 안나가지고 부분집합으로 먼저 해결했다

 

(반성해야할 부분)

 

하도 순열만 쓰다보니 조합이 생각이 안나더라

 

심플하게 배열을 모두 순회해서 모든 치킨집과 모든 집의 좌표를 찾는다

 

치킨 집 좌표 리스트에 넣을때마다, 치킨 집 개수도 세어준다

 

from sys import stdin

n,m = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

house_list = []
chicken = []
c = 0 #치킨 집의 개수

#모든 치킨집과 모든 집의 좌표를 찾는다
for y in range(n):
    
    for x in range(n):
        
        if maps[y][x] == 1:
            
            house_list.append((x,y))
        
        elif maps[y][x] == 2:
            
            chicken.append((x,y))
            c += 1

 

치킨 집 좌표 리스트에서 최대 m개를 선택한다

 

이거는 치킨 집 좌표 리스트에서, 모든 부분집합을 검사하는 것과 같다

 

min_value = 10000000000000000000000000000000

#부분 집합을 구하는 프로그램
for i in range(1<<c):
    
    partial = []

    k = 0

    for j in range(c):
        
        if i & (1<<j):
            
            partial.append(chicken[j])
            k += 1

 

부분집합의 크기가 m을 넘지 않아야한다

 

최대 m개만 선택한다 했으니까

 

크기가 m을 넘지 않는 부분집합에 대하여 치킨 거리를 구해본다

 

"어떤 집과 모든 치킨 집 사이 거리를 구해서, 최솟값이 그 집의 치킨거리"

 

그리고 치킨집 최소 1개는 뽑아야겠지.. 0개는 안될거고 

 

(근데 0개는 안된다는 말은 없긴한디 ㅋㅋㅋ)

 

아무튼 그러면 이중for문으로 집 좌표 리스트를 먼저 순회해서 집 좌표를 기준으로 하고

 

부분집합내에 든 모든 치킨집 좌표 리스트를 순회해서

 

집과 치킨집 사이 거리를 모두 구해본다음에 거기서 최솟값이 해당 집의 치킨거리

 

모든 집을 순회해보면서 도시 치킨거리에 집 치킨거리를 누적합해서, 최솟값을 갱신

 

#부분집합의 크기가 m이하이고, 1이상이면
    if k <= m and k >= 1:
        
        city_chicken = 0 #도시의 치킨거리

        for h_x,h_y in house_list: #집을 먼저 순회하고
            
            min_chicken = 100000000000000000000000000 #집의 치킨거리 최솟값 초기화
            
            for c_x,c_y in partial: #치킨집을 모두 순회해보고
                
                distance = (abs(c_x-h_x)+abs(c_y-h_y)) #치킨거리를 구한다음에

                if min_chicken > distance: #최솟값 갱신
                    
                    min_chicken = distance
            
            city_chicken += min_chicken #최솟값을 구했으면, 도시의 치킨거리에 더해준다
                
        if city_chicken < min_value: #현재 케이스의 도시 치킨거리 최솟값 갱신
            
            min_value = city_chicken


print(min_value)

 

 

전체 코드 써보면..

 

from sys import stdin

n,m = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

house_list = []
chicken = []
c = 0 #치킨집의 개수

#모든 치킨집과 모든 집의 좌표를 찾는다
for y in range(n):
    
    for x in range(n):
        
        if maps[y][x] == 1:
            
            house_list.append((x,y))
        
        elif maps[y][x] == 2:
            
            chicken.append((x,y))
            c += 1

min_value = 10000000000000000000000000000000

#부분 집합을 구하는 프로그램
for i in range(1<<c):
    
    partial = []

    k = 0

    for j in range(c):
        
        if i & (1<<j):
            
            partial.append(chicken[j])
            k += 1
            
#부분집합의 크기가 m이하이고, 1이상이면
    if k <= m and k >= 1:
        
        city_chicken = 0 #도시의 치킨거리

        for h_x,h_y in house_list: #집을 먼저 순회하고
            
            min_chicken = 100000000000000000000000000 #집의 치킨거리 최솟값 초기화
            
            for c_x,c_y in partial: #치킨집을 모두 순회해보고
                
                distance = (abs(c_x-h_x)+abs(c_y-h_y)) #치킨거리를 구한다음에

                if min_chicken > distance: #최솟값 갱신
                    
                    min_chicken = distance
            
            city_chicken += min_chicken #최솟값을 구했으면, 도시의 치킨거리에 더해준다
                
        if city_chicken < min_value: #현재 케이스의 도시 치킨거리 최솟값 갱신
            
            min_value = city_chicken


print(min_value)

 

 

부분집합으로 구하는건 솔직히 뭔가 아쉽다

 

조합이 기억이 안나서 차선책으로 푼거라

 

그래서 조합 구현한 재귀함수 사용해서도 풀어보았다

 

시간이 2배정도 빠르더라

 

확실히 부분집합 구할때 1<<c가 c가 너무 크면 오래걸릴것 같아

 

조합을 구현한 nCr을 다시한번 기억한다는 생각으로..

 

from sys import stdin

def nCr(n,r,s):
    
    global min_value
    
    #r개를 모두 뽑았다면
    #치킨 거리를 구해본다
    if r == 0:
        
        city_chicken = 0 #도시 치킨거리

        for h_x,h_y in house_list: #모든 집을 순회하고,
            
            min_chicken = 100000000000000000000000 #현재 집의 치킨거리 최솟값 초기화

            for c_x,c_y in comb: #i개를 뽑은 치킨 집 좌표 순회
                
                distance = (abs(c_x-h_x)+abs(c_y-h_y)) #치킨 거리 구해서

                if min_chicken > distance: #현재 집의 치킨거리 최솟값 갱신
                    
                    min_chicken = distance
            
            city_chicken += min_chicken #최솟값을 구했으면 도시 치킨거리에 누적합
        
        if min_value > city_chicken: #전체 도시 치킨거리 최솟값 초기화
            
            min_value = city_chicken
                
    else:
        
        #기본 조합 부분
        for i in range(s,n-r+1):
            
            comb[r-1] = chicken[i]

            nCr(n,r-1,i+1)

n,m = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

house_list = []
chicken = []
c = 0 #치킨집의 수

#모든 치킨집과 집 좌표를 찾는다
for y in range(n):
    
    for x in range(n):
        
        if maps[y][x] == 1:
            
            house_list.append((x,y))
        
        elif maps[y][x] == 2:
            
            chicken.append((x,y))
            c += 1

min_value = 10000000000000000000000000000000

#치킨집을 1개부터 m개 선택해서 모든 경우에 대해 치킨 거리를 구해본다
for i in range(1,m+1):
    
    comb = [0]*i #i개를 뽑아 치킨 좌표를 넣을 조합

    nCr(c,i,0)


print(min_value)

 

 

3. 되돌아보기

 

조합 다시한번 기억해주자

 

def nCr(n,r,s):

 

if r == 0:

print(comb)

 

else:

for i in range(s,n-r+1):

 

comb[r-1] = num_list[i]

 

nCr(n,r-1,i+1)

 

순열이랑 부분집합만 쓰다보니 조합은 생각이 안나던데

 

다시한번..

 

그 외에 어려운건 없었어

 

문제 항상 잘 읽어야하고