[Python] BOJ 17779 - 게리맨더링 2

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

17779번: 게리맨더링 2

# 2019년 하반기 삼성SW 역량테스트 문제이다.

# 문제를 이해하는데 오래 걸렸다. 그림만 보면 금방 이해가 갔을텐데, 글로 길게 써놓으니 헷갈렸다..

# 5개의 선거구로 나누고 각각의 선거구의 인구 합을 구한 뒤,

   인구가 가장 많은 선거구와 가장 작은 선거구의 인구 차이를 구하는 문제이다.

 

# (x, y, d1, d2) = (1, 1, 1, 1)부터 (N-2, N-2, N-2, N-2)까지 완전탐색을 돌려서 풀었다.

  * N이 20이하이고 d1, d2도 N-1이하이므로 4중for문을 돌려도 O(20x20x20x20)이다.

 

# i, j가 (1, N-1)인 이유는 (0, 0)과 같은 곳은 왼쪽이 무조건 맵 밖이므로 후보에서 제외된다.

   마찬가지로 가장자리의 좌표들은 모두 후보가 될 수 없다.

 

import sys
input = sys.stdin.readline
N = int(input())
m = [[0] * (N+2) for _ in range(N+2)]
tmp = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
	for j in range(N):
		m[i+1][j+1] = tmp[i][j]

def get_people(i, j, d1, d2):
	# t가 1부터 N까지 증가하면서 각 선거구의 인구를 구해줌.
	for t in range(1, N+1):
		
		# 맨 위의 5번좌표 이전까지 1, 2구역 인구 구하기
		if t < i:
			people[1] += sum(m[t][ :j+1])
			people[2] += sum(m[t][j+1: ])
		
		# 맨 위 5번좌표부터 맨 왼쪽 5번좌표 이전까지 1 구역 인구 구하기
		if i <= t < i + d1:
			people[1] += sum(m[t][ :j-(t-i)])
		
		# 맨 왼쪽 5번좌표부터 맨 아래쪽 5번좌표까지 3 구역 인구 구하기
		if i + d1 <= t <= i + d1 + d2:
			people[3] += sum(m[t][ :j-d1+d2-(i+d1+d2-t)])
		

		# 맨 위의 5번좌표부터 맨 오른쪽 5번좌표까지 2 구역 인구 구하기	
		if i <= t <= i + d2:
			people[2] += sum(m[t][j+(t-i)+1: ])

		# 맨 오른쪽 5번좌표 다음부터 맨 아래쪽 5번좌표까지 4 구역 인구 구하기
		if i + d2 < t <= i + d1 + d2:
			people[4] += sum(m[t][j-d1+d2+(i+d1+d2-t)+1: ])
		
		# 맨 아래쪽 5번좌표 다음부터 끝까지 3, 4구역 인구 구하기
		if i + d1 + d2 < t:
			people[3] += sum(m[t][ :j-d1+d2])
			people[4] += sum(m[t][j-d1+d2: ])

		# 5번 구역 인구는 d1과 d2의 대소관계에 따라 약간 달라진다.
		if d1 >= d2:
			if i <= t < i + d1:
				people[5] += sum(m[t][j-(t-i): j+(t-i)+1])
			if i + d1 <= t <= i + d1 + d2:
				people[5] += sum(m[t][j-d1+d2-(i+d1+d2-t): j-d1+d2+(i+d1+d2-t)+1])
		else:	
			if i <= t <= i + d1:
				people[5] += sum(m[t][j-(t-i): j+(t-i)+1])
			if i + d1 < t <= i + d1 + d2:
				people[5] += sum(m[t][j-d1+d2-(i+d1+d2-t): j-d1+d2+(i+d1+d2-t)+1])

dab = 987654321
for i in range(1, N-1):
	for j in range(1, N-1):
		for d1 in range(1, N-1):
			# x좌표가 맵 밖을 벗어나면 break, 아니면 d2까지 check
			if i + d1 > N-1 or j - d1 < 0:
				break
			for d2 in range(1, N-1):
				people = [0, 0, 0, 0, 0, 0]
				# y좌표가 맵 밖을 벗어나면 break, 아니면 모든 구역이 맵 안에 있으므로 get_people 함수실행
				if i + d2 > N or j + d2 > N:
					break
				get_people(i, j, d1, d2)

				# diff = 인구가 가장 많은 선거구 - 인구가 가장 적은 선거구
				# dab에는 diff의 최솟값이 갱신된다.
				diff = max(people[1:]) - min(people[1:])
				if dab > diff:
					dab = diff
print(dab)

(solved.ac 티어: 골드 4)

 

# 구역이 대각선으로 나뉘어져 있어서 get_people함수에서 case를 나누는데 엄청 시간이 걸렸다.

   또한, 5번 구역은 d1 > d2일때와 d1 < d2일때가 또 달라서 한번 더 케이스를 나누어주었다.

 

# 최근 푼 문제중 가장 오랜시간을 소요한 것 같다..(2시간 정도)

   case를 많이 나눈 만큼 코드는 길어진 것 같지만, 실행속도는 생각보다 빨랐다. (python3 20등)