2학년 2학기 알고리즘 과제_6주차(백준_1098번:쌍둥이 마을)

1098번: 쌍둥이 마을

 

 

 

 

문제

쌍둥이 마을은 두 마을의 사람들 간에 커뮤니케이션과 문화적 교류를 위해서 만든 것이다.

따라서 정부는 마을 사이에 쌍둥이 마을을 많이 제정하려고 한다. 물론 가능한 모든 마을의 쌍을 쌍둥이 마을로 제정하면 좋겠지만, 다음과 같은 규칙을 지켜야 한다.

1. 각 마을은 P개 이하의 쌍둥이 마을을 가진다. 쌍둥이 마을이 없을 수도 있다.
2. 각 쌍둥이 마을의 거리는 적어도 D이다.두 마을이 (x1, y1) 과 (x2, y2) 에 있을 때, 두 마을 사이의 거리는 |x1-x2| + |y1-y2|이다.

정부는 되도록이면 많은 쌍둥이 마을을 만들려고 한다. 만약 이러한 것이 여러 가지라면, 쌍둥이 마을 사이의 거리의 합을 최소로하는 것을 선택한다. 각 마을의 위치와 P와 D가 주어질 때, 쌍둥이 마을의 개수의 최댓값과 그 때 쌍둥이 마을 사이의 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 마을의 좌표가 주어진다. x좌표와 y좌표 순서대로 주어지며, 각 좌표는 1,000보다 작거나 같은 자연수 또는 0이다. 마지막 줄에는 P와 D가 주어진다. P는 3보다 작거나 같은 자연수이고, D는 2,000보다 작거나 같은 자연수이다. 두 도시의 위치가 중복되는 경우는 없다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

 

📎문제 풀이 ( 내생각 및 기타 )

 

 

문제를 풀기위한 제약조건은 다음과 같다.

 

• 한 마을은 최대 PPP개의 쌍둥이 마을을 가질 수 있다.
• 두 마을 사이의 거리는 DDD 이상이어야 한다.
• 가능한 가장 많은 쌍둥이 마을을 만들고, 이때 거리 합이 최소가 되어야한다.

 

해당 문제의 특징은 다음과 같다.

• N≤10N \leq 10N≤10이므로 가능한 모든 조합을 탐색할 수 있는 완전 탐색과 동적 프로그래밍(DP) 접근법해야한다.
• 두 마을 간 거리 계산은 맨해튼 거리를 사용해야한다.

 

문제 풀이 목표

• 연결된 쌍둥이 마을의 최대 개수 flow\text{flow}flow를 구하기
• 이때 거리 합 cost\text{cost}cost를 최소화하기

 

 

 

📎 코드 분석

 

import sys
from itertools import product

def main():
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    x, y = [], []
    for i in range(1, n + 1):
        x_coord, y_coord = map(int, data[2 * i - 1:2 * i + 1])
        x.append(x_coord)
        y.append(y_coord)
    p, d = map(int, data[2 * n + 1:])
    
    pmx = 1 << (n + n)
    dp = [float('inf')] * pmx
    dp[0] = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(x[i] - x[j]) + abs(y[i] - y[j])
            if dist < d:
                continue
            x_idx, y_idx = i, j
            for mask in range(pmx - 1, -1, -1):
                if ((mask >> (x_idx + x_idx)) & 3) == p or ((mask >> (y_idx + y_idx)) & 3) == p:
                    continue
                nmask = mask + (1 << (x_idx + x_idx)) + (1 << (y_idx + y_idx))
                dp[nmask] = min(dp[nmask], dp[mask] + dist)
    
    flow = 0
    cost = float('inf')
    for mask in range(pmx):
        if dp[mask] == float('inf'):
            continue
        popcnt = sum((mask >> (i + i)) & 3 for i in range(n))
        if popcnt % 2 or flow > popcnt // 2:
            continue
        if flow == popcnt // 2:
            cost = min(cost, dp[mask])
        else:
            flow = popcnt // 2
            cost = dp[mask]
    
    print(flow, cost)

if __name__ == "__main__":
    main()

 

 

 

• n은 마을의 개수를 나타내는 변수이다.
• 각 마을의 좌표를 리스트 x와 y에 저장한다.
• p는 각 마을이 가질 수 있는 최대 연결 수, d는 최소 거리 제한을 위한 변수이다.

 

• DP 배열 초기화
  • dp 배열은 가능한 모든 상태에 대한 최소 비용을 저장
  • 초기 상태는 dp[0] = 0이고, 나머지는 무한대로 초기화

 

• 마을 쌍 처리
  • 가능한 모든 마을 쌍을 고려해야하는데, 쌍의 거리 dist가 최소 거리 d 이상인 경우만 처리한다.
  • 각 쌍을 연결했을 때의 새로운 상태(nmask)와 최소 비용을 갱신하도록한다.

 

• 최종 결과 계산
  • 모든 상태를 확인하여, 가능한 최대 연결 수(flow)와 최소 비용(cost)를 계산한다.

 

 

📎 느낀점

 

 

허헛 결과는 실패인데,!!! 다른 사람 코드를 보고 추가 공부를 해보려하였으나,, 없다 푼사람이..!

일단 플래티넘인거 보니까 어려운게 맞다.

알고리즘을 풀어도 늘기는 생각보다 쉽지않다는 생각.. 모든 문제가 새롭다!!