코딩하는 덕구 🐶

130. [삼성기출26]Python 백준 17779 번 게리맨더링 2 본문

알고리즘 문제 풀이

130. [삼성기출26]Python 백준 17779 번 게리맨더링 2

코딩하는 덕구 🐶 2023. 6. 26. 15:40
728x90

안녕하세요 코딩하는 덕구입니다.

백준 17779 게리맨더링 2 입니다.

제 코드는 파이썬으로 선택하면 시간초과가 뜹니다.

 

게리맨더링은 특정 정당의 선거 결과를 유리하게 만들기 위해 의도적으로 선거구를 나누는 것을 말합니다.

각설하고 백준 17779번 게리맨더링 코드입니다. 설명은 아래에 있습니다.

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

ans = 1e9

def bfs(x, y, terri):
    queue = deque()
    queue.append([x, y])
    terri[x][y] = 5
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if terri[nx][ny] == 0:
                    terri[nx][ny] = 5
                    queue.append([nx, ny])


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) and (y - d1) >= 0 and (y + d2) < N:

                    terri = [[0 for _ in range(N)] for _ in range(N)]

                    for d1_i in range(d1 + 1):
                        terri[x + d1_i][y - d1_i] = 5

                    for d2_i in range(d2 + 1):
                        terri[x + d2_i][y + d2_i] = 5

                    for i3 in range(d2 + 1):
                        terri[x + d1 + i3][y - d1 + i3] = 5

                    for i4 in range(d1 + 1):
                        terri[x + d2 + i4][y + d2 - i4] = 5

                    for i in range(N):
                        for j in range(N):
                            flag = True
                            for ii in range(4):
                                nx = dx[ii] + i
                                ny = dy[ii] + j
                                if 0 <= nx < N and 0 <= ny < N:
                                    if terri[nx][ny] == 0:
                                        flag = False
                                else:
                                    flag = False

                            if flag:
                                terri[i][j] = 5

                    bfs(x + 1, y, terri)

                    popu = [0 for _ in range(5)]

                    for r in range(N):
                        for c in range(N):
                            if terri[r][c] == 5:
                                popu[4] += board[r][c]

                            if terri[r][c] != 5:
                                if r < (x + d1) and 0 <= c <= y:
                                    popu[0] += board[r][c]
                                elif r <= (x + d2) and y < c < N:
                                    popu[1] += board[r][c]
                                elif (x + d1) <= r < N and c < y-d1 + d2:
                                    popu[2] += board[r][c]
                                elif (x + d2) < r < N and (y - d1 + d2) <= c < N:
                                    popu[3] += board[r][c]

                    ans = min(max(popu) - min(popu), ans)

print(ans)

 

문제 접근

1. 선거구를 나누는 모든 경우의 수를 구합니다.

2. 그 중 선거구들의 최대값 - 최소값이 최소가 되는 값을 출력합니다.

 

제 풀이의 경우 5번 선거구의 테두리를 입력받고 내부를 5번 선거구로 채운 후

1~ 4번 선거구 만들어 count했습니다.

 

Python 코드 구현

 먼저 필요한 라이브러리를 불러온 후 선거 구를 입력받습니다.

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

ans = 1e9

 

 모든 x, y, d1, d2의 경우를 지정하고 만약 조건에 맞다면 선거구를 나눕니다.

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) and (y - d1) >= 0 and (y + d2) < N:

 

 선거구의 테두리를 그립니다.

terri = [[0 for _ in range(N)] for _ in range(N)]

for d1_i in range(d1 + 1):
    terri[x + d1_i][y - d1_i] = 5

for d2_i in range(d2 + 1):
    terri[x + d2_i][y + d2_i] = 5

for i3 in range(d2 + 1):
    terri[x + d1 + i3][y - d1 + i3] = 5

for i4 in range(d1 + 1):
    terri[x + d2 + i4][y + d2 - i4] = 5

 

태두리의 내부를 채웁니다. 두 가지의 경우가 있습니다. (bfs로 채우려고 했으나 1번 조건 때문에 불 충분 합니다.)

1. 상하좌우 모두가 5번 선거구인 경우

for i in range(N):
    for j in range(N):
        flag = True
        for ii in range(4):
            nx = dx[ii] + i
            ny = dy[ii] + j
            if 0 <= nx < N and 0 <= ny < N:
                if terri[nx][ny] == 0:
                    flag = False
            else:
                flag = False

        if flag:
            terri[i][j] = 5

 

2. 상하좌우 하나라도 5번 선거 구가 아닌경우

bfs(x + 1, y, terri)

def bfs(x, y, terri):
    queue = deque()
    queue.append([x, y])
    terri[x][y] = 5
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if terri[nx][ny] == 0:
                    terri[nx][ny] = 5
                    queue.append([nx, ny])

 

 

 5번의 선거구의 인원과 1, 2, 3, 4 번의 선거구의 인원을 count 해줍니다.

popu = [0 for _ in range(5)]

for r in range(N):
    for c in range(N):
        if terri[r][c] == 5:
            popu[4] += board[r][c]

        if terri[r][c] != 5:
            if r < (x + d1) and 0 <= c <= y:
                popu[0] += board[r][c]
            elif r <= (x + d2) and y < c < N:
                popu[1] += board[r][c]
            elif (x + d1) <= r < N and c < y-d1 + d2:
                popu[2] += board[r][c]
            elif (x + d2) < r < N and (y - d1 + d2) <= c < N:
                popu[3] += board[r][c]

 

 이렇게 답을 업데이트 하며 최소값을 출력하면 됩니다.

                    ans = min(max(popu) - min(popu), ans)

print(ans)

 

파이썬 백준 17779 게리맨더링 최종 코드입니다. 

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

ans = 1e9

def bfs(x, y, terri):
    queue = deque()
    queue.append([x, y])
    terri[x][y] = 5
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if terri[nx][ny] == 0:
                    terri[nx][ny] = 5
                    queue.append([nx, ny])


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) and (y - d1) >= 0 and (y + d2) < N:

                    terri = [[0 for _ in range(N)] for _ in range(N)]

                    for d1_i in range(d1 + 1):
                        terri[x + d1_i][y - d1_i] = 5

                    for d2_i in range(d2 + 1):
                        terri[x + d2_i][y + d2_i] = 5

                    for i3 in range(d2 + 1):
                        terri[x + d1 + i3][y - d1 + i3] = 5

                    for i4 in range(d1 + 1):
                        terri[x + d2 + i4][y + d2 - i4] = 5

                    for i in range(N):
                        for j in range(N):
                            flag = True
                            for ii in range(4):
                                nx = dx[ii] + i
                                ny = dy[ii] + j
                                if 0 <= nx < N and 0 <= ny < N:
                                    if terri[nx][ny] == 0:
                                        flag = False
                                else:
                                    flag = False

                            if flag:
                                terri[i][j] = 5

                    bfs(x + 1, y, terri)

                    popu = [0 for _ in range(5)]

                    for r in range(N):
                        for c in range(N):
                            if terri[r][c] == 5:
                                popu[4] += board[r][c]

                            if terri[r][c] != 5:
                                if r < (x + d1) and 0 <= c <= y:
                                    popu[0] += board[r][c]
                                elif r <= (x + d2) and y < c < N:
                                    popu[1] += board[r][c]
                                elif (x + d1) <= r < N and c < y-d1 + d2:
                                    popu[2] += board[r][c]
                                elif (x + d2) < r < N and (y - d1 + d2) <= c < N:
                                    popu[3] += board[r][c]

                    ans = min(max(popu) - min(popu), ans)

print(ans)

 

백준 177779 게리맨더링 Python 코드였습니다.

감사합니다.

728x90
저작자표시 (새창열림)

'알고리즘 문제 풀이' 카테고리의 다른 글

132. [삼성기출28]Python 백준 17822 번 원판 돌리기  (0) 2023.07.04
131. [삼성기출27]Python 백준 17837 번 새로운 게임 2  (0) 2023.07.03
129. [삼성기출25]Python 백준 17142 번 연구소 3  (0) 2023.06.23
128. [삼성기출24]Python 백준 17140 번 이차원 배열과 연산  (0) 2023.06.21
127. [삼성기출23]Python 백준 17143 번 낚시왕  (0) 2023.06.13
'알고리즘 문제 풀이' Related Articles more