[Python] 백준 17417 게리맨더링

문제 링크 : https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

1. 접근 방법

 주어진 점으로 이루어진 그래프를 두 개의 부분 그래프로 나누는 문제인데, 다른 조건이 없다 보니 모든 경우의 수를 탐색해야 한다. 다행히도 점이 최대 10개만 주어지므로 큰 어려움 없이 해결할 수 있다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/17000/17400/17471.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

def make_section(N: int, comb: tuple) -> list:
    section = [1] * (N + 1)
    section[0] = 3
    for x in comb:
        section[x] = 2
    return section


def search(
    N: int, sections: list[list[int]], populations: list[int], section: list[int]
) -> tuple[int]:
    pop_a = pop_b = 0
    visited = [False] * (N + 1)
    visited[0] = True
    queue = deque([section.index(1), section.index(2)])
    while queue:
        x = queue.popleft()
        if visited[x]:
            continue
        visited[x] = True
        s = section[x]
        if s == 1:
            pop_a += populations[x]
        elif s == 2:
            pop_b += populations[x]
        for y in sections[x]:
            if section[y] != s:
                continue
            if not visited[y]:
                queue.append(y)
    if all(visited):
        return pop_a, pop_b
    else:
        return 0, 0


def get_diff(x: int, y: int) -> int:
    return abs(x - y)


if __name__ == "__main__":
    N = int(input())
    populations = [0] + list(MIIS())
    sections = [[]]
    for i in range(N):
        _, *section = MIIS()
        sections.append(list(section))
    ans = 1000
    for i in range(1, N):
        for comb in combinations(range(1, N + 1), i):
            section = make_section(N, comb)
            x, y = search(N, sections, populations, section)
            if not x and not y:
                continue
            tmp = get_diff(x, y)
            if ans > tmp:
                ans = tmp
    print(ans if ans != 1000 else -1)

 

📕코드 해설

 우선 입력을 받고, itertools.combinations를 활용해서 진행했다. 만약 이를 활용하지 않았다면 DFS로 구성했을 것 같다. 각각의 그룹에는 1개 이상의 점이 있어야 하므로 1개의 점부터 확인하기 시작했다. 여기서 특정 그룹의 점은 구했는데, 다른 그룹의 점을 구하지 않고 탐색하기는 어렵다고 느꼈다.

 

def make_section(N: int, comb: tuple) -> list:
    section = [1] * (N + 1)
    section[0] = 3
    for x in comb:
        section[x] = 2
    return section

 그래서 이 함수를 작성하여, 어떠한 점이 어떤 그룹에 속하는지 판별했다. section이라는 리스트를 만들어 1번 또는 2번 구역에 속하게 작업했고, 0번점은 탐색하는데 문제가 발생하기도 하여 3번으로 두어 전혀 상관없는 값으로 주었다.

 이후 search함수는 일반적인 BFS로 구성했다. 위에서 구한 두 그룹 중 1번 구역과 2번 구역에 속하는 하나의 점을 구하고, 모든 구역을 탐색할 수 있는지 확인한다. 이때, 특정 점이 속하는 그룹 기준으로 같은 그룹일 때만 queue에 추가하여 탐색했고, 마지막으로 모든 점의 탐색이 끝났다면 각 그룹의 인구를 반환한다.

 

---

3. 생각 정리

 조합을 더욱 효율적으로 구성하는 방법은 고민했는데, 다른 방법이 떠오르지는 않았다. 조합뿐만 아니라 그래프 탐색도 더 효율적인 방식을 고민하게 된다.