게리 맨더링2_재도전

못 푼 이유

SWEA 모의고사 디저트 카페 문제 풀고, 게리 맨더링2 문제 또한 비슷한 방법으로 풀 수 있을 것이라고 생각했다. 디저트 카페처럼 5번 선거구 경계라인을 선택하는 것은 출력해봄으로써 잘 한것을 확인할 수 있었는데, 각 경우마다 선거구 별로 인구수를 구하는 것이 좀 어려웠다.

문제->추상화->코드 단계 중에서 추상화한 것을 코드로 구현해내는 것. 재귀함수를 깊이 있게 이해하지 못하는 건 아닐까 생각도 들었다.

방향 전환이 일어날 때, 꼭짓점이 생기기 때문에 그 때의 좌표를 컬렉션에 따로 저장하여 이 컬렉션에 저장된 좌표를 이용하여 1,2,3,4 선거구마다 인구수를 구할 수 있을 거라 생각했다.

재귀가 일어날 때마다 그 때의 좌표(nx,ny)를 컬렉션에 저장하고, 재귀함수가 리턴 될 때 컬렉션에서 삭제처리했다. 사각형을 완성한 경우, 컬렉션의 갯수는 시작점을 제외하고 3개가 출력되는 것을 확인했다. 그런데 시작점을 하나 추가하니까 3개 또는 4개로 값이 일정하지 않게 나왔다. 4개로 일관되게 나와야 정상인데 말이다.

다른 코드나 풀이 영상을 보니까, d1, d2에 대해서도 선택의 범위를 처리해주는 것 같다. 디저트 카페는 경계선만 찾으면 되기 때문에 재귀함수로 간단하게 처리가 가능했지만, 게리 맨더링2문제는 그 때의 사각형 경우, 구역마다 인구수를 구해야하기 때문에 경계선을 기준으로 선거구를 나누고, 그 선거구 마다 인구수를 구하 것이 큰 차이점이다.

따라서 x,y,d1,d2 각 4개의 수에 대해 문제에서 제시된 조건을 걸어주고, 그 조건을 만족하는 숫자들로 조합을 만들면 된다.

na 982님의 문제 접근 방법. 풀이 방법

조건에 맞는 x,y,d1,d2를 모두 골라낸다. 골라낸 x,y,d1,d2를 이용해서 선거구를 5개로 나눈다. 각각 선거구에 인구수의 합을 구하고, 가장 큰 값과 가장 작은 값의 차를 계산한다.

시간 복잡도 계산

1. x,y,d1,d2를 선택하는 경우의 수 : 20^4 //왜 20이지? N=20이니까 각 숫자마자 20*20=400개의 경우의 수가 있는 거 아닌가?

2. 각 케이스마다 인구수 합 계산하기 위해 20*20 연산이 필요하다.

3. 따라서 1번 * 2번 = 20^4 * 20 * 20 = 약 20^6 = 약 6400만 이론적으로는 이렇지만 x,y,d1,d2의 모든 숫자가 되는 것은 아니기 때문에 정확한 계산이 필요하다. na 982님 코드로 계산을 해보면 1번이 10830, 2번 20*20 으로, 최종 시간 복잡도는 433만 2000이 나온다. 따라서 그냥 하면 된다!

수식이나 선거구 범위 조건을 문제에서 주었다. 그렇기 때문에 x,y를 원하는 대로 쓰지 말고, 문제에서 정해준 대로 쓰는 것이 가장 깔끔하다. 예를 들어 축을 비틀어서 x,y를 바꿔서 사용하면 오류가 나기 쉽고, 그러면 코드 상으로 오류를 찾기 힘들다. 이 말인 즉슨, 시험 칠 때 디버깅으로 찾을 수가 없게 된다.

따라서 문제에서 주어지는 좌표가 어떻게 되어있는지 정확하게 알고 넘어가는 것이 중요하다. x와 r : 아래 방향으로 증가, y와 c : 오른쪽 방향으로 증가

• 1번 선거구 : 1 <= r < x+d1, 1<= c <=y

• 2번 선거구 : 1 <= r <= x+d2, y< c <=N

• 3번 선거구 : x+d1 <= r <=N-1, 1<= c < y-d1+d2

• 4번 선거구 : x+d2 < r <= N, y-d1+d2 <= c <= N

인구수 구하기 : 문제에서 주어진 4개의 선거구 범위에 따라 각 선거구의 인구수를 구하면 된다. 1,3 선거구 : 2중 for문으로 왼쪽에서 오른쪽으로, 위에서 아래로 2차원 배열을 순회하다가, 5를 만나면 다음행으로 넘어가도록 구현한다. 2,4 선거구 : 반대로 x는 증가하되, y는 감소하는 방향으로 진행하고, 동일하게 5를 만나면 다음행으로 넘어가도록. 5구역은 전체 합 - (1,2,3,4 구역 합)으로 구하면 된다.

구현 : 처음부터 끝까지 날 것 그대로 구현하는 순서.

1. 경계선 선택하기

   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)

d1선택할 때, x+d1은 어디까지 내려올 수 있나? x+d1은 선거구1과 3의 꼭짓점이다. 따라서 x+d1은 N-2까지 내려올 수 있다. 열 y-d1은 어디까지 가능한가? 0 이상이여야 한다. x,y for문을 어렵지 않게 구성했다면, 이 x,y와 문제에서 주어진 경계선 선택 방법에 따라 d1도 범위를 설정할 수 있다.

아래 꼭짓점과 좌표를 통해 d2범위도 설정할 수있다.

x,y,d1,d2 4중 for문을 구현했으면 각각의 경우마다 선거구를 마킹하는 2차원 배열 또한 초기화해야한다. Arrays.fill로 할 수 있다.

for(int i=0;i<N;i++) {
							Arrays.fill(Area[i], 0);
						}

먼저, 5번 선거구 경계부터 2차원 배열 Area에 마킹한다.

그리고 경계선 규칙 1,2,3,4 그대로 구현해주면 된다. 경계선1과 경계선 2의 경우 변위값이 단순히 d1과 d2이기 때문에 Area[x+i][y-i], (i는 d1이 증가하는 반복 변수) , Area[x+i][y+i] (i는 d2가 증가하는 반복 변수)로 구현 가능하다. 하지만 경계선 3과 4의 경우, 각 경계선의 시작에 중점을 두지 말고, 끝까지 변화하는 값을 보고, 변화해가는 변위값을 중점적으로 보자. 그러면 경계선 3의 변위값은 d2로 인해 변화해가고, 경계선 4의 변위값은 d1으로 인해 변화해간다는 것을 알 수 있다. 즉, 경계선 3,4를 설정할 때 중요한 것은 시작점이 아니라 변화하는 값, d1 또는 d2이다!

1. (x,y)에서 시작, (x+d1,y-d1)으로 변화 => 변위값 d1

2. (x,y)에서 시작, (x+d2,y+d2)으로 변화 => 변위값 d2

3. (x+d1,y-d1)에서 시작, (x+d1+d2,y-d1+d2)으로 변화 => 변위값 d2

4. (x+d2,y+d2)에서 시작, (x+d2+d1,y+d2-d1)으로 변화 => 변위값 d1

경계선을 다 마킹하고나면, 각 전체 NxN의 4개 꼭짓점은 해당 선거구 번호를 의미하기 때문에 해당 꼭짓점에서 시작하여 나머지 구역의 선거구 번호도 마킹할 수 있다.