BOJ - 게리맨더링2 17779번 (python, JAVA)

❓ 문제 - 백준 게리맨더링2 17779번 - python, JAVA 풀이법

 

출처 

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

17779번: 게리맨더링 2

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 재현시의 격자의 각 칸에 해당하는 인구수의 정보를 입력받고, total 변수에 총 인구수를 저장한다.
• 일단 문제에서 주어진 기준점(x,y)와 경계의 길이(d1, d2)의 범위 안에서 해당하는 수를 조건에 맞춰서 다섯 개의 선거구로 나눈 후 선거구의 차이가 가장 작은 수를 계속 갱신하면서 정답을 출력한다.
• 기준점(x, y)와 경계의 길이(d1, d2)의 범위는 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 이므로 4중 포문(1 ~ n+1) 돌면서 x+d1+d2 > n, y-d1 < 1, y + d2 > n의 경우는 범위를 벗어나므로 선거구의 인구수 차이를 계산하지 않고 나머지 경우엔 선거구의 인구수 차이를 계산한다.
• x, y, d1, d2에서 선거구를 나눌 땐, 일단 경계선을 만들어야 하는데 경계선을 만들 때 조건은 문제에서 주어진 2번 조건으로 5번 선거구의 경계선을 표시한다.
• 그 다음은 1 ~ 4번 선거구를 찾기 위해 문제 4번에서 주어진 조건의 범위를 이용하여 1 ~ 4번 선거구를 표시한다. 해당 선거구의 지역을 구하기 위해서 선거구의 조건의 범위 안에 들 때, 해당 칸의 인구수를 더해준다. 만약 해당 범위를 돌면서 5번 즉, 경계선을 만나면 인구수를 더해주지 않고 break를 해준다.
• 1, 3 선거구는 열에서 오른쪽으로 가면서 해당 범위에 해당되는지 파악한 후 인구수를 더해주며 경계선을 만나면 다음 행에 대해 파악한다. 2, 4 선거구는 열은 왼쪽으로 가면서 해당 범위에 해당되는지 파악하며 인구수를 더해주며 만약 경계선을 만나면 다음 행에 대해 파악한다.
• 전체 인구 수(total) 에서 구한 1,2,3,4 선거구의 인구수를 빼서 5 선거구의 인구수를 구한다.
• 5개의 선거구에서 최대 인구수의 선거구와 최소 인구수의 선거구를 빼서 최소 인구수의 차이를 갱신하며 구한다.

 

 

💻 소스코드 (python)

n = int(input())
graph = [[0 for _ in range(n+1)]]
total = 0

for i in range(n):
    data = [0] + list(map(int, input().split()))
    total += sum(data)
    graph.append(data)

min_diff = int(1e9)

def solve(x, y, d1, d2):
    global min_diff
    g = [[0]*(n+1) for _ in range(n+1)]
    people = [0, 0, 0, 0, 0]
    # 경계선 그리기
    g[x][y] = 5
    for i in range(1, d1+1):
        g[x+i][y-i] = 5
    for i in range(1, d2+1):
        g[x+i][y+i] = 5
    for i in range(1, d2+1):
        g[x+d1+i][y-d1+i] = 5
    for i in range(1, d1+1):
        g[x+d2+i][y+d2-i] = 5


    # 1
    for i in range(1, x+d1):
        for j in range(1, y+1):
            if g[i][j] == 5:
                break
            else:
                people[0] += graph[i][j]

    # 2
    for i in range(1, x+d2+1):
        for j in range(n, y, -1):
            if g[i][j] == 5:
                break
            else:
                people[1] += graph[i][j]

    # 3
    for i in range(x+d1, n+1):
        for j in range(1, y-d1+d2):
            if g[i][j] == 5:
                break
            else:
                people[2] += graph[i][j]
    # 4
    for i in range(x+d2+1, n+1):
        for j in range(n, y-d1+d2-1, -1):
            if g[i][j] == 5:
                break
            else:
                people[3] += graph[i][j]

    people[4] = total - sum(people[0:4])
    min_diff = min(min_diff, max(people)-min(people))

for x in range(1, n+1):
    for y in range(1, n+1):
        for d1 in range(1, n+1):
            for d2 in range(1, n+1):
                if x+d1+d2 > n:
                    continue
                if y-d1 < 1:
                    continue
                if y + d2 > n:
                    continue
                solve(x, y, d1, d2)

print(min_diff)

 

 

💻 소스코드 (JAVA)

// BOJ - 게리멘더링2(17779번)
// 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_17779 {
	public static int[][] map;
	public static int n, total, ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		for(int i=1;i<=n;i++) {
			String[] data = br.readLine().split(" ");
			for(int j=1;j<=n;j++) {
				map[i][j] = Integer.parseInt(data[j-1]);
				total += map[i][j];
			}
		}
		ans = Integer.MAX_VALUE;
		for(int x=1;x<=n;x++) {
			for(int y=1;y<=n;y++) {
				for(int d1=1;d1<=n;d1++) {
					for(int d2=1;d2<=n;d2++) {
						if(x+d1+d2 > n) continue;
						if(y-d1 < 1) continue;
						if(y+d2 > n) continue;
						solve(x, y, d1, d2);
					}
				}
			}
		}
		System.out.println(ans);


	}

	public static void solve(int x, int y, int d1, int d2) {
		int[][] map2 = new int[n+1][n+1];
		int[] people = new int[5];

		// 경계선 그리기
		map2[x][y] = 5;
		for(int i=1;i<=d1;i++) {
			map2[x+i][y-i] = 5;
		}

		for(int i=1;i<=d2;i++) {
			map2[x+i][y+i] = 5;

		}

		for(int i=1;i<=d2;i++) {
			map2[x+d1+i][y-d1+i] = 5;
		}

		for(int i=1;i<=d1;i++) {
			map2[x+d2+i][y+d2-i] = 5;
		}

		// 1선거구
		for(int i=1;i<x+d1;i++) {
			for(int j=1;j<=y;j++) {
				if(map2[i][j] == 5) break;
				people[0] += map[i][j];
			}
		}

		// 2선거구
		for(int i=1;i<=x+d2;i++) {
			for(int j=n;j>y;j--) {
				if(map2[i][j] == 5) break;
				people[1] += map[i][j];
			}
		}

		// 3선거구
		for(int i=x+d1;i<=n;i++) {
			for(int j=1;j<y-d1+d2;j++) {
				if(map2[i][j] == 5) break;
				people[2] += map[i][j];
			}
		}

		// 4선거구
		for(int i=x+d2+1;i<=n;i++) {
			for(int j=n;j>=y-d1+d2;j--) {
				if(map2[i][j] == 5) break;
				people[3] += map[i][j];
			}
		}

		people[4] = total - (people[0] + people[1] + people[2] + people[3]);
		int min = Integer.MAX_VALUE;
		int max = 0;
		for(int i=0;i<5;i++) {
			max = Math.max(max, people[i]);
			min = Math.min(min, people[i]);
		}

		ans = Math.min(ans, max-min);


	}



	}