백준 게리맨더링 2 [17779] 파이썬(Python) 코드 + 해설

백준 게리맨더링 2 17779 문제

문제 설명

재현시는 𝑁 × 𝑁  크기의 격자로 표현되며, 각 격자는 구역을 의미합니다. 각 구역에는 인구수가 주어집니다. 시장은 공정한 선거구 획정을 위해 다음과 같은 규칙으로 다섯 개의 선거구로 나누려고 합니다.

1. 기준점 ( 𝑥,𝑦 )와 경계의 길이 𝑑1,𝑑2를 정합니다. (1≤𝑥<𝑥+𝑑1+𝑑2≤𝑁, 1≤𝑦−𝑑1<𝑦<𝑦+𝑑2≤𝑁, 𝑑1,𝑑2≥1)
2. 경계선을 긋습니다:
   • 1번 경계선: (𝑥,𝑦)부터 (𝑥+𝑑1 , 𝑦−𝑑1) 까지 대각선
   • 2번 경계선: (𝑥,𝑦)부터 (𝑥+𝑑2,  𝑦+𝑑2) 까지 대각선
   • 3번 경계선: (𝑥+𝑑1,𝑦−𝑑1)부터  𝑥+𝑑1+𝑑2, 𝑦−𝑑1+𝑑2)까지 대각선
   • 4번 경계선: (𝑥+𝑑2,𝑦+𝑑2) 부터 ( 𝑥+𝑑2+𝑑1, 𝑦+𝑑2-𝑑1)까지 대각선
3. 경계선과 그 안에 포함된 구역은 5번 선거구로 설정합니다.
4. 나머지 구역은 다음 기준에 따라 1번부터 4번 선거구로 분할합니다:
   • 1번 선거구: 1≤𝑟<𝑥+𝑑1, 1≤𝑐≤𝑦
   • 2번 선거구: 1≤𝑟≤𝑥+𝑑2, 𝑦<𝑐≤𝑁
   • 3번 선거구: 𝑥+𝑑1≤𝑟≤𝑁, 1≤𝑐<𝑦−𝑑1+𝑑2
   • 4번 선거구: 𝑥+𝑑2≤𝑟≤𝑁, 𝑦−𝑑1+𝑑2≤𝑐≤𝑁

선거구를 나눈 후, 각 선거구의 인구수를 계산하고, 가장 많은 인구를 가진 선거구와 가장 적은 인구를 가진 선거구의 인구 차이를 구합니다. 이 인구 차이의 최솟값을 구하는 것이 문제의 목표입니다.

문제 접근

문제에서 요구하는 것은 가능한 모든 x, 𝑦, 𝑑1, 𝑑2의 조합을 탐색하여 인구 차이의 최솟값을 찾는 것입니다. 이를 위해 다음과 같은 단계로 접근합니다:

1. 가능한 모든 x, 𝑦, 𝑑1, 𝑑2 조합 탐색:
   • x 는 1부터 𝑁 - 2까지
   • 𝑦 는 2부터 𝑁 - 1까지
   • 𝑑1 과 𝑑2 는 1부터 𝑁 - 1까지
   • 조건을 만족하는 𝑑1 , 𝑑2 에 대해 탐색
2. 선거구 경계 설정 및 구역 분할:
   • 경계선을 그려 5번 선거구를 설정
   • 나머지 구역을 1번부터 4번 선거구로 분할
3. 각 선거구의 인구수 계산:
   • 각 선거구에 속하는 구역의 인구수를 합산
4. 인구 차이 계산 및 최솟값 갱신:
   • 최대 인구수와 최소 인구수의 차이를 계산
   • 최솟값을 갱신

구현 상세

1. 입력 및 초기화

N = int(input())
population = [list(map(int, input().split())) for _ in range(N)]

 

• 𝑁 : 격자의 크기
• population: 각 구역의 인구수를 저장한 2차원 리스트

2. 가능한 모든 조합 탐색

min_diff = float('inf')

for x in range(N):
    for y in range(N):
        for d1 in range(1, N):
            for d2 in range(1, N):
                if x + d1 + d2 >= N:
                    continue
                if y - d1 < 0 or y + d2 >= N:
                    continue
                divide_and_calculate(x, y, d1, d2)

• 가능한 모든 x, 𝑦, 𝑑1, 𝑑2  조합을 탐색하며 조건을 만족하는 경우에만 진행

3. 선거구 분할 및 인구수 계산 함수

def divide_and_calculate(x, y, d1, d2):
    board = [[0]*N for _ in range(N)]

    # 경계선 표시 (5번 선거구)
    for i in range(d1+1):
        board[x + i][y - i] = 5
        board[x + d2 + i][y + d2 - i] = 5
    for i in range(d2+1):
        board[x + i][y + i] = 5
        board[x + d1 + i][y - d1 + i] = 5

    # 선거구 번호 할당
    # 1번 선거구
    for r in range(x + d1):
        for c in range(y + 1):
            if board[r][c] == 5:
                break
            board[r][c] = 1
    # 2번 선거구
    for r in range(x + d2 + 1):
        for c in range(N - 1, y, -1):
            if board[r][c] == 5:
                break
            board[r][c] = 2
    # 3번 선거구
    for r in range(x + d1, N):
        for c in range(y - d1 + d2):
            if board[r][c] == 5:
                break
            board[r][c] = 3
    # 4번 선거구
    for r in range(x + d2 + 1, N):
        for c in range(N - 1, y - d1 + d2 - 1, -1):
            if board[r][c] == 5:
                break
            board[r][c] = 4
    # 5번 선거구
    for r in range(N):
        for c in range(N):
            if board[r][c] == 0:
                board[r][c] = 5

    # 각 선거구의 인구수 계산
    total = [0]*5
    for r in range(N):
        for c in range(N):
            total[board[r][c]-1] += population[r][c]

    diff = max(total) - min(total)
    global min_diff
    if diff < min_diff:
        min_diff = diff

• board: 각 구역의 선거구 번호를 저장하는 2차원 리스트
• 경계선을 따라 5번 선거구를 표시
• 각 선거구에 속하는 구역을 할당
• 각 선거구의 인구수를 계산하여 인구 차이의 최솟값을 갱신

4. 결과 출력

print(min_diff)

 

백준 17779 게리맨더링 2 파이썬(Python) 정답 코드

N = int(input())
population = [list(map(int, input().split())) for _ in range(N)]
min_diff = float('inf')

def divide_and_calculate(x, y, d1, d2):
    board = [[0]*N for _ in range(N)]

    # 경계선 표시 (5번 선거구)
    for i in range(d1+1):
        board[x + i][y - i] = 5
        board[x + d2 + i][y + d2 - i] = 5
    for i in range(d2+1):
        board[x + i][y + i] = 5
        board[x + d1 + i][y - d1 + i] = 5

    # 선거구 번호 할당
    # 1번 선거구
    for r in range(x + d1):
        for c in range(y + 1):
            if board[r][c] == 5:
                break
            board[r][c] = 1
    # 2번 선거구
    for r in range(x + d2 + 1):
        for c in range(N - 1, y, -1):
            if board[r][c] == 5:
                break
            board[r][c] = 2
    # 3번 선거구
    for r in range(x + d1, N):
        for c in range(y - d1 + d2):
            if board[r][c] == 5:
                break
            board[r][c] = 3
    # 4번 선거구
    for r in range(x + d2 + 1, N):
        for c in range(N - 1, y - d1 + d2 - 1, -1):
            if board[r][c] == 5:
                break
            board[r][c] = 4
    # 5번 선거구
    for r in range(N):
        for c in range(N):
            if board[r][c] == 0:
                board[r][c] = 5

    # 각 선거구의 인구수 계산
    total = [0]*5
    for r in range(N):
        for c in range(N):
            total[board[r][c]-1] += population[r][c]

    diff = max(total) - min(total)
    global min_diff
    if diff < min_diff:
        min_diff = diff

for x in range(N):
    for y in range(N):
        for d1 in range(1, N):
            for d2 in range(1, N):
                if x + d1 + d2 >= N:
                    continue
                if y - d1 < 0 or y + d2 >= N:
                    continue
                divide_and_calculate(x, y, d1, d2)

print(min_diff)

 

백준 17779 게리맨더링 2 문제 파이썬 제출 결과

백준 17779 게리맨더링 2 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.