99클럽 코테 스터디 _ 15일차 TIL (브루트 포스, 조합)

 

< 문제 >

[백준] 15686. 치킨 배달 / 골드5

---

< 풀이 >

코드 변수 정의

• chickens : 치킨집 좌표 리스트
• houses : 집 좌표 리스트
• min_dist : 최종 반환할 최소 치킨 거리
• total_dist : 치킨집 조합별 총 치킨 거리
• house_to_chicken : 현재 집의 치킨 거리

---

Brute Force
시간복잡도 : O(C(13,M)×(H×M))≈O(10^6)

from itertools import combinations

def chicken():
    N, M = map(int, input().split()) # 도시 크기 NxN, 선택할 치킨집 개수 M
    board = [list(map(int, input().split())) for _ in range(N)] # 도시 정보 입력
	
    # 치킨집과 집의 좌표 저장
    chickens = [(i, j) for i in range(N) for j in range(N) if board[i][j] == 2]
    houses = [(i, j) for i in range(N) for j in range(N) if board[i][j] == 1]

    min_dist = float('inf') # 최소 치킨 거리 초기화
    
    # 모든 치킨집 조합에서 M개 선택
    for selected in combinations(chickens, M):
        total_dist = 0 # 현재 조합에서의 총 치킨 거리
        
        # 각 집에 대해 가장 가까운 치킨집과의 거리 계산
        for hx, hy in houses:
            house_to_chicken = float('inf') # 현재 집의 최소 치킨 거리
            for cx, cy in selected:
                house_to_chicken = min(house_to_chicken, abs(hx - cx) + abs(hy - cy))
            total_dist += house_to_chicken # 전체 거리 합산
        
        # 최소 치킨 거리 갱신
        min_dist = min(min_dist, total_dist)
    
    print(min_dist)

chicken()

---

 

 

 

풀이 방식

1. 입력 처리
   • NxN 크기의 board를 입력받아 집(1)과 치킨집(2)의 좌표를 저장한다.
2. 가능한 치킨집 조합 생성
   • combiinations로 M개의 치킨집을 선택하는 모든 경우를 탐색한다.
   • 치킨집이 5개이고 M=3이면, 5개 중 3개를 선택하는 모든 조합 C(5,3) = 10개를 생성한다.
3. 각 조합에 대한 최소 치킨 거리 계산
   • 각 집에 대해 선택된 치킨집과의 거리 중 가장 짧은 값을 찾는다.
   • 맨해튼 거리를 사용하여 계산한다.
     • d = |x1 - x2| + |y1 - y2|
   • min()으로 현재까지 찾은 가장 짧은 거리를 저장한다.
   • 모든 집의 치킨 거리 합을 구한다.
4. 최소 치킨 거리 갱신
   • 현재 조합에 대한 total_dist값을 min_dist와 비교하여 더 작은 값을 저장한다.
   • 모든 조합을 탐색한 후 min_dist를 출력하여 정답을 도출한다.

---

< 회고 >

🤔 💭_

치킨집이 최대 13개까지 주어지기 때문에 combinations로 가능한 모든 치킨집 조합을 구하는 방식으로 계산하고자 했다. 치킨집을 선택한 후, 각 집을 탐색하며 선택된 치킨집들로 치킨 거리를 구하고 모든 집의 치킨 거리 합을 구하는 방식으로 해결했다.

---

순열과 조합

product('ABCD', repeat = 2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD

---

백트래킹 풀이 방식

def chicken():
    
    # 선택된 치킨집들과 각 집 사이의 최소 거리를 계산하여 총 치킨 거리를 반환
    def calculate_distance(selected_chickens):
        total_dist = 0
        for hx, hy in houses:
            house_to_chicken = float('inf')  # 현재 집에서 가장 가까운 치킨집 거리
            for cx, cy in selected_chickens:
                house_to_chicken = min(house_to_chicken, abs(hx - cx) + abs(hy - cy))
            total_dist += house_to_chicken  # 모든 집의 최소 거리 합산
        return total_dist
        
    # 백트래킹을 활용하여 M개의 치킨집을 선택하는 함수
    def backtrack(start, selected):
        nonlocal min_dist
        if len(selected) == M:  # M개의 치킨집을 선택한 경우
            min_dist = min(min_dist, calculate_distance(selected))  # 최소 거리 갱신
            return
        
        # 백트래킹을 이용하여 치킨집 선택
        for i in range(start, len(chickens)):
            backtrack(i + 1, selected + [chickens[i]])
    
    N, M = map(int, input().split())  # 도시 크기 N×N, 선택할 치킨집 개수 M
    board = [list(map(int, input().split())) for _ in range(N)]  # 도시 정보 입력
    
    # 치킨집과 집의 좌표 저장
    chickens = [(i, j) for i in range(N) for j in range(N) if board[i][j] == 2]
    houses = [(i, j) for i in range(N) for j in range(N) if board[i][j] == 1]
    
    min_dist = float('inf')  # 최소 치킨 거리 초기화
    
    # 백트래킹을 이용한 치킨집 선택
    backtrack(0, [])
    
    print(min_dist)

chicken()