[시뮬레이션] 대각선 경계 좌표 구하기 (BOJ 17779 게리맨더링 2)

(1,1)부터 시작하는 격자가 주어지고, 대각선 경계를 가지는 마름모꼴 영역이 주어진다.

이 영역만 색칠하고 싶을 때, 어떻게 조건문을 짜야 대각선 경계를 처리할 수 있을까?

 

판에 대각선을 그려가며 패턴을 파악해보자.

 

우상향하는 대각선에 있는 칸들은 좌표합 x + y이 일정하다는 특징을 가진다.

우하향하는 대각선에 있는 칸들은 좌표차 y - x이 일정하다.

 

BOJ 17779 게리맨더링 2 문제는 기준점 (x_s, y_s)에서 d1, d2만큼 대각선으로 떨어진 지점을 잡고 마름모를 그린다.

위에서 파악한 대각선 경계 특징을 활용하여, 마름모 영역을 다음과 같은 조건문으로 잡아낼 수 있다.

int diag1 = x_s + y_s, diag2 = y_s - x_s;

// x, y는 각각 [1, N] 범위 내 수; 2중 For문으로 iterate (생략)
if ((diag1 <= x + y && x + y <= diag1 + 2*d2) 
  && (diag2 - 2*d1 <= y - x && y - x <= diag2)){
  	// 구역 5 (마름모 꼴 구역) 처리
}

처음엔 이걸 몰라서, 시작점에서 d1, d2 떨어진 지점까지 경계선을 하나씩 찍고,

각 행마다 경계선이 시작해서 끝날 때까지 칸들을 색칠해서 마름모를 말 그대로 '색칠'함.

하드 코딩이기에 코드도 길어지고 시간도 오래 걸리니, 이 방법 잘 숙지해두기!

 

---

(15Apr21 수정) 각 라인에 있는 원소의 개수가 필요하다면?

 

좌표합 x + y 혹은 y - x 와 원소의 개수 간의 관계를 이끌어내기는 힘들어보인다.

이럴 때는 직접 수를 나열해서 패턴을 찾아보자.

 

대각선 ↗ 의 좌표합 x + y => 원소 개수

1 + 1  =>  1

1 + 2  =>  2

1 + 3  =>  3

...

1 + N  =>  N

2 + N  =>  N-1

3 + N  =>  N-2

...

N-1 + N  =>  2  

N + N  => 1

 

패턴을 보고 식을 끼워맞춰보자.

좌표합을 K라고 하자.

K <= N+1 일때, 원소 개수 = K-1

K > N+1 일때, 원소 개수 = N - (K - N - 1) = 2*N - K + 1

 

 

대각선 ↘ 의 좌표합 y - x => 원소 개수

N - 1  =>  1

N - 2  =>  2

N - 3  =>  3

...

N - N  =>  N

(N-1) - N  =>  N-1

(N-2) - N  =>  N-2

...

2 - N  =>  2  

1 - N  => 1

 

K >= 0 일때, 원소 개수 = - K

K < 0 일때, 원소 개수 = K + N