[BOJ] 게리맨더링2


  • BOJ의 게리맨더링2 문제 풀이입니다

문제 풀이

  • 해당 문제를 풀기 위해서는 다음과 같은 단계를 거쳐야 합니다
  1. 5번 선거구의 경계선을 표시한다
  2. 5번 선거구 경계선 안에 있는 지역을 5번 선거구로 표시해준다
  3. 1~4번 선거구의 구역안에서 5번 선거구에 표시 되지 않는 구역을 각각 표시해준다
  • 우선 입력을 받아서 선거구를 표시해줄 행렬을 만들어줍니다

import sys

N = int(sys.stdin.readline())

matrix = []
for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

  • 그리고 d1과 d1를 정해주는데, d1과 d1는 1 이상의 갑싱고 x와 y의 조건에서 알 수 있듯이 x와 y는 N이하의 값을 가지기 때문에 d1, d2는 다음과 같이 N미만의 조합으로 생길 수 있습니다
d_list = []
for i in range(1, N):
    for j in range(1, N):
        d_list.append([i,j])
maxdiff = float('inf') # 선거구 차이를 비교하기 위한 값


for i in range(len(d_list)):
    d1, d2 = d_list[i] # 반복을 통해 d1, d2를 선택해준다
    #x와 y는 d1, d2를 더해주는데, 이 값이 N 이하의 값을 가지므로 N 미만의 범위를 갖는다
    for x in range(1, N):
        for y in range(1, N):
            # d1, d2에 대해 x, y의 조건의 만족하는 경우
            if(x < x+d1+d2 and x+d1+d2 <= N and 1<=y-d1 and y-d1 < y and y< y+d2 and y+d2 <=N):
                # x,y와 행렬의 인덱스 위치를 맞추기 위해 N+1의 행렬을 만들어준다
                district = [[0]*(N+1) for _ in range(N+1)]

                for i in range(d1+1):
                    district[x+i][y-i] = 5 # 1번 경계선
                    district[x+d2+i][y+d2-i] = 5 # 4번 경계선

                for i in range(d2+1):
                    district[x+i][y+i] = 5 # 2번 경계선
                    district[x+d1+i][y-d1+i] = 5 # 3번 경계선

                # 5번 선거구의 안을 5로 표시해준다
                # d1 방향 (1, 4 선거구) - 왼쪽 아래 방향으로
                # 경계선 한칸 아래의 값부터 5를 만날 때 까지 5로 표시해준다
                for d in range(d1):
                    i = 1
                    while(district[x+d+i][y-d] != 5):
                        district[x+d+i][y-d] = 5
                        i+=1
                #d2 방향 (2, 3 선거구) - 오른쪽 아래 방향으로
                # 경계선 한칸 아래의 값부터 5를 만날 때 까지 5로 표시해준다
                for d in range(d2):
                    i = 1
                    while(district[x+d+i][y+d] != 5):
                        district[x+d+i][y+d] = 5
                        i+=1

                # 1번 선거구
                for r in range(1, x+d1):
                    for c in range(1, y+1):
                        if(district[r][c] == 0):
                            district[r][c] = 1

                # 2번 선거구
                for r in range(1, x+d2+1):
                    for c in range(y, N+1):
                        if(district[r][c] ==0):
                            district[r][c] = 2

                 # 3번 선거구
                for r in range(x+d1, N+1):
                    for c in range(1, y-d1+d2):
                        if(district[r][c] == 0):
                            district[r][c] = 3

                # 4번 선거구
                for r in range(x+d2+1, N+1):
                    for c in range(y-d1+d2, N+1):
                        if(district[r][c] == 0):
                            district[r][c] = 4


                count = [0,0,0,0,0]


                for i in range(1, N+1):
                    for j in range(1, N+1):
                        if(district[i][j] == 1):
                            count[0] += matrix[i-1][j-1]
                        elif(district[i][j] ==2):
                            count[1]+=matrix[i-1][j-1]
                        elif(district[i][j]==3):
                            count[2]+=matrix[i-1][j-1]
                        elif(district[i][j]==4):
                            count[3]+=matrix[i-1][j-1]
                        else:
                            count[4]+=matrix[i-1][j-1]




                if (max(count) - min(count) < maxdiff):
                    maxdiff = max(count) - min(count)


print(maxdiff)

전체 코드


import sys

N = int(sys.stdin.readline())

matrix = []
for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))




d_list = []
#x 와 y 범위 조건에 따라 x, y 는 N이 될 수 없다
for i in range(1, N):
    for j in range(1, N):
        d_list.append([i,j])


maxdiff = float('inf')
for i in range(len(d_list)):
    d1, d2 = d_list[i]
    for x in range(1, N):
        for y in range(1, N):
            if(x < x+d1+d2 and x+d1+d2 <= N and 1<=y-d1 and y-d1 < y and y< y+d2 and y+d2 <=N):
                district = [[0]*(N+1) for _ in range(N+1)]

                for i in range(d1+1):
                    district[x+i][y-i] = 5 # 1번 경계선
                    district[x+d2+i][y+d2-i] = 5 # 4번 겨예선

                for i in range(d2+1):
                    district[x+i][y+i] = 5 # 2번 경계선
                    district[x+d1+i][y-d1+i] = 5 # 3번 경계선


                # d1 방향 (1, 4 선거구 )
                for d in range(d1):
                    i = 1
                    while(district[x+d+i][y-d] != 5):
                        district[x+d+i][y-d] = 5
                        i+=1
                #d2 방향 (2, 3 선거구 )
                for d in range(d2):
                    i = 1
                    while(district[x+d+i][y+d] != 5):
                        district[x+d+i][y+d] = 5
                        i+=1

                # 1번 선거구
                for r in range(1, x+d1):
                    for c in range(1, y+1):
                        if(district[r][c] == 0):
                            district[r][c] = 1

                # 2번 선거구
                for r in range(1, x+d2+1):
                    for c in range(y, N+1):
                        if(district[r][c] ==0):
                            district[r][c] = 2

                 # 3번 선거구
                for r in range(x+d1, N+1):
                    for c in range(1, y-d1+d2):
                        if(district[r][c] == 0):
                            district[r][c] = 3

                # 4번 선거구
                for r in range(x+d2+1, N+1):
                    for c in range(y-d1+d2, N+1):
                        if(district[r][c] == 0):
                            district[r][c] = 4


                count = [0,0,0,0,0]


                for i in range(1, N+1):
                    for j in range(1, N+1):
                        if(district[i][j] == 1):
                            count[0] += matrix[i-1][j-1]
                        elif(district[i][j] ==2):
                            count[1]+=matrix[i-1][j-1]
                        elif(district[i][j]==3):
                            count[2]+=matrix[i-1][j-1]
                        elif(district[i][j]==4):
                            count[3]+=matrix[i-1][j-1]
                        else:
                            count[4]+=matrix[i-1][j-1]




                if (max(count) - min(count) < maxdiff):
                    maxdiff = max(count) - min(count)


print(maxdiff)


BOJ - 게리맨더링 2







© 2020. by dkmqflx

Powered by dkmqflx