개구리

우물 안 개구리

문제를 풀다보면 조합이 필요한데 이 때 가장 많은 의문이 들었다. 하지만 구현 문제라는 것을 알고 풀었기 때문에 차근차근 코드를 작성했다. https://gudals113.github.io/algorithm/acmicpc-21608/ 21608번 상어 초등학교 문제 풀 때도 그랬지만 의문이 생겨서 시간이 정체되는 것이 구현 문제의 함정인 것 같다.

from itertools import combinations

N, M = map(int, input().split())
# city = [ [ 0 for _ in range(N) ] for _ in range(N)]

loc_chicken = []
loc_house = []

for i in range(N):
    line = list(map(int, input().split()))
    for j in range(N) :
        w = line[j]
        # city[i][j] = w
        if w ==1:
            loc_house.append([i,j])
        elif w == 2:
            loc_chicken.append([i,j])
                
distance_htoc=[]

#집에서 치킨집까지 모든 거리 구하기 O(2N * 13)
for house in loc_house : 
    x, y = house[0], house[1]
    tmp=[]
    for chicken in loc_chicken : 
        a,b = chicken[0], chicken[1]
        dis = abs(x-a) + abs(y-b)
        
        tmp.append(dis)
        
    distance_htoc.append(tmp)

# print(distance_htoc)

op=1
ans = float('INF')
len_house = len(loc_house)
len_chicken = len(loc_chicken)

while op <= M :
    comb = list( combinations( [ i for i in range(len_chicken) ], op ) )
    
    for i in range(len(comb)): 
        toleft = comb[i]  # 총 개수가 op개인 조합들 toleft = (0,1) (1,2) (0,2)
        
        sol=0       
        for j in range(len_house): #집에서 치킨집까지 거리 리스트 모든 집에 대하여 루프
            
            tmp_j=2*N
            for e in (toleft) :  # 조합에서 고를 수 있는 치킨 집 인덱스 e
                tmp_j = min(tmp_j, distance_htoc[j][e])

            sol+=tmp_j
            
            

        ans = min(ans, sol)           
    
    
    op+=1

print(ans)

python의 라이브러리를 사용하여 조합을 구현한다. 처음에는 조합을 구현하는 것이 문제의 핵심인가 생각이 들었는데 일단 라이브러리를 사용하여 풀었다.

문제 설계

일반적인 그래프 문제와 다르게 주어진 격자를 모두 사용하지 않고 치킨집과 집의 위치만 각각 loc_chicken, loc_house 배열에 표시했다.

distance_htoc 배열에 모든 치킨집과 집에 대하여 치킨 거리를 저장한다. ex) distance_htoc[0][2] : 0번 집에서 2번 집까지의 치킨 거리. (0번부터 시작하도록 설계했다)

구현

  1. 최대 M개의 치킨집을 남길 수 있으므로 치킨집이 1개일 때부터 M개일 때까지 루프를 돌린다. 현재 운영 중인 치킨집의 개수를 op라는 변수에 저장했다.
  2. 전체 치킨집에서 op개의 치킨집의 개수를 뽑을 수 있는 조합을 comb에 배열 형태로 저장했다. ex)op=3일 때 [(0, 1, 2), (0, 1, 3), …] 와 같이 저장된다.
  3. comb내의 i 번째 순서쌍을 toleft에 저장한다. ex)i=0일 때, toleft = (0,1)
  4. 집에서 순서쌍 내의 치킨집까지의 거리 중 최솟값을 tmp_j에 저장한다.
  5. 모든 집에 대하여 루프를 돌려 sol에 더해 나간다. 모든 집이 같은 치킨집을 선택하지 않고 각자의 집에서 가장 가까운 치킨거리가 더해지는 것이다.
  6. 모든 조합에 대하여 루프를 돌려 ans를 갱신해 나간다.
  7. ans를 출력한다.

수정된 코드

시간 복잡도를 줄일 수 있는 방법이 있지 않을까. 백준 pypy3 풀이 기준 해당 풀이는 시간복잡도 측면에서 빠른 편이 아니다. 1번에서 1에서 M까지 루프를 돌리지 않고 M개일 때만 실행한다. 치킨집이 최대한 영업 중일때 최적의 답이 나올 수 있다는 것은 자명하기 때문이다.

from itertools import combinations

N, M = map(int, input().split())
# city = [ [ 0 for _ in range(N) ] for _ in range(N)]

loc_chicken = []
loc_house = []

for i in range(N):
    line = list(map(int, input().split()))
    for j in range(N) :
        w = line[j]
        # city[i][j] = w
        if w ==1:
            loc_house.append([i,j])
        elif w == 2:
            loc_chicken.append([i,j])
                
distance_htoc=[]

#집에서 치킨집까지 모든 거리 구하기 O(2N * 13)
for house in loc_house : 
    x, y = house[0], house[1]
    tmp=[]
    for chicken in loc_chicken : 
        a,b = chicken[0], chicken[1]
        dis = abs(x-a) + abs(y-b)
        
        tmp.append(dis)
        
    distance_htoc.append(tmp)

ans = float('INF')
len_house = len(loc_house)
len_chicken = len(loc_chicken)

comb = list( combinations( [ i for i in range(len_chicken) ], M ) )
# print(comb)
for i in range(len(comb)): 
    toleft = comb[i]  # 총 개수가 op개인 조합들 toleft = (0,1) (1,2) (0,2)
    
    sol=0       
    for j in range(len_house): #집에서 치킨집까지 거리 리스트 모든 집에 대하여 루프
        
        tmp_j=2*N
        for e in (toleft) :  # 조합에서 고를 수 있는 치킨 집 인덱스 e
            tmp_j = min(tmp_j, distance_htoc[j][e])
        sol+=tmp_j
        
        
    ans = min(ans, sol)           

print(ans)

댓글남기기

참고