17779: 게리맨더링 2

https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

설명

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

 

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

핵심 아이디어

이 문제는 완전탐색, 구현 문제이다. 기준점 x,y와 경계의 길이 d1,d2가 가질수 있는 모든 조합을 다 탐색해서 선거구끼리 인구수 차이의 최솟값을 구해주면 된다. 각 변수들이 가질 수 있는 범위는 1 ~ n 까지이고, 문제에서 제공한 변수의 조건만 만족하면 모두 후보가 될 수 있다. 모든 조합을 탐색하면서 함수를 실행시켜 최솟값을 업데이트해주면 된다. 

 

함수: 선거구당 인구수를 저장하는 배열과 각 좌표가 어떤 선거구인지를 알려주는 배열을 선언한다. 입력으로 들어온 x,y,d1,d2에 대해서 경계선에 해당하는 부분을 5번 선거구로 지정해준다. 그 다음 경계선 내부에 대해서는 행을 탐색하면서 경계선을 만나면 그 다음 경계선을 만날때까지 5번 선거구로 지정해주면되는데, 이는 bool값을 이용하면 된다. 그리고 5번 선거구를 구했으면, 5번 선거구에 포함되지 않은 영역중 각 선거구의 범위에 해당하는 부분을 지정해 주면 된다.

1. 선거구당 인구수, 각 좌표가 어떤 선거구인지 알려주는 배열 선언
2. 5번 선거구를 먼저 지정해 준다.
3. 그 후 나머지 선거구를 지정해 주면 된다.

코드 구현

1. 초기 맵 선언하고 입력받기

처음에 맵을 설정하는 과정에서 1번 index부터 시작하기 위해 조정을 고려하여 맵을 설정했는데, index 범위 초과 결과가 나서 잠깐 헷갈렸었다.

n = int(input())
graph = [[]]
for _ in range(n):
    graph.append([0] + list(map(int, input().split())))
'''
[]
[0, 1, 2, 3, 4, 1, 6]
[0, 7, 8, 9, 1, 4, 2]
[0, 2, 3, 4, 1, 1, 3]
[0, 6, 6, 6, 6, 9, 4]
[0, 9, 1, 9, 1, 9, 5]
[0, 1, 1, 1, 1, 9, 9]
'''

n = int(input())
graph = [[0] + list(map(int, input().split())) for _ in range(n)]
'''
[0, 1, 2, 3, 4, 1, 6]
[0, 7, 8, 9, 1, 4, 2]
[0, 2, 3, 4, 1, 1, 3]
[0, 6, 6, 6, 6, 9, 4]
[0, 9, 1, 9, 1, 9, 5]
[0, 1, 1, 1, 1, 9, 9]
'''

2. 완전 탐색

ans = int(1e9)
# 완전 탐색: 기준점, 경계 조합을 모두 탐색해서 각 조합마다 최소시간을 비교해서 업데이트
for x in range(1, n+1):
    for y in range(1, n+1):
        # d1,d2 >= 1
        for d1 in range(1, n+1):
            for d2 in range(1, n+1):
                # 주어진 조건을 만족한다면
                    if (1 <= x < x + d1 + d2 <= n) and (1 <= y-d1<y<y+d2<=n):
                        ans = min(ans, cal(x,y,d1,d2))
print(ans)

주어진 조건 1을 잘 파악해서 작성하면 된다.

3. 주거진 조건에 따라 선거구를 나누고 최대인원 최소인원의 차를 구하느 함수

def cal(x,y,d1,d2):
    # 각 선거구 마다 총 인원을 저장하는 배열
    arr = [[0] for _ in range(5)] # 선거구는 1 ~ 5로 총 5개
    # 선거구
    temp = [[0] * (n+1) for _ in range(n+1)]
    
    # 먼저 5번 선거구를 지정한다. 경계 구하기
    for i in range(d1+1): 
        temp[x+i][y+i] = 5 # 1번 조건
        temp[x+d2+i][y+d2-i] = 5 # 3번 조건
    # 
    for i in range(d2+1): # 기준점 계산을 위해 0부터 시작
        temp[x+i][y+i] = 5 # 2번 조건
        temp[x+d1+i][y+i-d1] =5  # 4번 조건
    # 5번 경계선 내부에 5번 선거구 할당
    for i in range(x + 1, x + d1 + d2):  # 예시 1번 기준 행 3,4,5
        flag = False
        # 행을 기준으로 한번 경계 구역을 만나면
        for j in range(1, n + 1):
            if temp[i][j] == 5: # 경계
                flag = not flag # 다시 경계구역을 만날 때 까지
            if flag:
                temp[i][j] = 5 # 5번 구역
    # 이제 선거구 지정하기
    for r in range(1, n+1):
        for c in range(1, n+1):
            if r < x + d1 and c <= y and temp[r][c] == 0: # 5번 선거구가 아니라는 뜻
                arr[0] += graph[r][c] # 1번 선거구
            elif r <= x + d2 and y < c and temp[r][c] == 0:
                arr[1] += graph[r][c] # 2번 선거구
            elif x + d1 <= r and c < y - d1 + d2 and temp[r][c] == 0:
                arr[2] += graph[r][c] # 3번 선거구
            elif x + d2 < r and y - d1 + d2 <=c and temp[r][c] == 0:
                arr[3] += graph[r][c]
            elif temp[r][c] == 5: # 5번 선거구라면
                arr[4] += graph[r][c]
    return max(arr) - min(arr)

여기서 주의할 점은 flag = True로 바꾸면 안된다. not flag라 해야지 처음 이후의 5번 경계를 다시 만났을 때 False로 바꾸어 5를 영역안에 넣는 반복과정을 멈추게 된다.