[구름톤 챌린지] 4주차_중첩 점

 

필요한 개념

---

• 동적 프로그래밍

 

 

문제 분석

---

한 변의 길이가 N인 정사각형을 격자 모양으로 바꾼 뒤, M개의 직선을 규칙에 따라서 그린다.

이때 직선들끼리 교차하는 교점의 개수를 세는 문제이다.

 

완전 탐색을 활용한다면, (y, x) 에서 시작하는 직선을 그리려고 할 때, 그려진 직선을 모두 알아야 한다.

(y, x)에서 상/하로 그려질 직선은 좌/우로 그려진 직선의 개수만큼 점이 생기고, 좌/우로 그려질 직선은 상/하로 그려진 직선의 개수만큼 점이 발생한다.

그렇다면 주어지는 직선의 개수가 100,000 이기 때문에, 시간이 아주 오래걸릴 수 있다.

그래서 이 문제는 이전 계산을 기록하면서 현재의 계산을 간소화하는 방법이 필요한 동적 프로그래밍 문제이다.

 

 

규칙 이해하기

---

(3, 2) 칸을 지나는 두 개의 가로선이 있고, 이때 세로선을 그리면 두 개의 교점이 발생

(2, 1), (2, 2), (2, 3)을 지나는 두 개의 가로선과 각 칸을 지나는 세로선이 한 개씩 있으므로, 교점은 각 칸에서 두 개씩 총 여섯 개가 생김

 

• (y, x) 칸에서 위/아래 방향으로 그리는 선이 생기면, 해당 칸부터 끝까지 있는 모든 칸의 가로선의 개수가 발생하는 교점의 개수이다.
• (y, x) 칸에서 좌/우 방향으로 그리는 선이 생기면, 해당 칸부터 끝까지 있는 모든 칸의 세로 선의 개수가 발생하는 교점의 개수이다.

 

 

3차원 매트릭스

---

결과적으로 어떤 선을 그었을 때, 선이 이동하는 경로에 선의 개수만 알고 있어도 생기는 점의 개수를 구할 수 있다.

다만 가로선이라면 세로선의 개수가 필요하고, 세로선이면 가로선의 개수를 알아야 한다.

이를 구별해서 선의 개수를 관리해야 하므로 3차원 매트릭스로 구현한다.

 

가장 먼저 행렬을 2개 구현한다.

각 행렬은 세로선, 가로선만 관리하는 행렬이다.

// verMatrix : 어떤 좌표에서 세로 선의 개수만 관리
let verMatrix = new Array(N + 1).fill(null).map(() => new Array(N + 1).fill(0));
// horMatrix : 어떤 좌표에서 로 선의 개수만 관리
let horMatrix = new Array(N + 1).fill(null).map(() => new Array(N + 1).fill(0));

 

verMatrix 과 horMatrix 을 모두 관리할 수 있는 DP 변수를 만든다.

let dp = new Array(2);
dp[0] = verMatrix;
dp[1] = horMatrix;

 

꼭 배열로 만들 필요는 없고, 구조를 작성하고 싶은 방법에 따라 기록을 저장할 구조를 작성하면 된다.

일반적인 행렬을 작성한 뒤, 각각 요소에 넣을 데이터가 [선의 개수, 방향]으로 해도 된다.

let dp = new Array(N + 1).fill(null).map(() => new Array(N + 1).fill(0));
dp[1][1] = [3, 'V']; // (1, 1) 위치의 좌표에 세로 선이 3개 있음

 

 

기록하기

---

이제부터 진행되는 선 긋기를 중첩 기록할 수 있는 dp 라는 자료형을 선언했으니 기록만 하면 된다.

그 전에 dp[0] 에 할당된 매트릭스에는 세로 선만 기록하고, dp[1] 에 할당된 매트릭스에는 가로선만 기록한다.

2 1 R 라면, (2, 1) 좌표에서 오른쪽 끝으로 이동한다.

수평 이동을 하기 때문에 y 좌표는 동일하게 x 좌표는 2는 N 까지 선을 그을 수 있다.

/*
xPos = command의 x 좌표
yPos = Command의 y 좌표 
dp[1]에 들어있는 가로 표시만 기록하는 매트릭스의 새로운 선을 그림
dp[1][yPos][i] 값 1 추가
*/ 
for (let i = xPos; i <= N; i++) {
	dp[1][yPos][i] += 1;
}

 

선을 그리는 것도 중요하지만, 발생하는 중첩 점의 개수를 세는 것도 중요하다.

R 이라는 명령어는 가로로 그리는 선이기 때문에 세로 선의 개수가 중첩 점을 만든다.

세로 선은 dp[0] 에 있다는 사실을 알고 있다면, 선이 지나는 칸에 그려진 세로 선의 개수를 알 수 있다.

/*
xPos = command의 x 좌표
yPos = Command의 y 좌표 
spot_count = 중첨 점의 개수
dp[0]에 들어있는 세로 선 기록하는 매트릭스의 값을 꺼냄
spot_count 값을 매트릭스 값 만큼 추가
*/ 
for (let i = xPos; i <= N; i++) {
	spot_count += dp[0][yPos][i];
	dp[1][yPos][i] += 1;
}

 

좌표를 이동시키는 명령어를 완성한다.

U, D: x 좌표는 고정, y 좌표가 N으로 가거나 1로 감

R, I: y 좌표는 고정, x 좌표가 N으로 가거나 1로 감

for (let i = 1 ; i <= M ; i++){
		// 명령어 입력
		const [y, x, dir] = input[i];
		// 문자열을 정수로 전환 Number 사용 가능
		let xPos = parseInt(x);
		let yPos = parseInt(y);

		/* 
		D 나 U 의 경우, 
		spot_count는 가로 선을 관리하는 DP[1]에서 추출
		DP 갱신은 세로 선을 관리하는 DP[0]을 갱신
		*/ 
		if (dir === "D") {
			for (let i = yPos; i <= N; i++) {
				spot_count += dp[1][i][xPos];
				dp[0][i][xPos] += 1;
			}
		} 
		else if (dir === "U") {
			for (let i = 1; i <= yPos; i++) {
				spot_count += dp[1][i][xPos];
				dp[0][i][xPos] += 1;
			}
		} 

		/* 
		R 나 L 의 경우, 
		spot_count는 세로 선을 관리하는 DP[0]에서 추출
		DP 갱신은 가로 선을 관리하는 DP[1]을 갱신
		*/ 
		else if (dir === "R") {
			for (let i = xPos; i <= N; i++) {
				spot_count += dp[0][yPos][i];
				dp[1][yPos][i] += 1;
			}
		} 
		else if (dir === "L") {
			for (let i = 1; i <= xPos; i++) {
				spot_count += dp[0][yPos][i];
				dp[1][yPos][i] += 1;
			}
		}
	}

 

이 계산이 끝난 뒤에 spot_count를 출력한다.

 

 

 

이 문제는 규칙을 이해하는 것과, 어떤 방법으로 구현해야 할지가 어려웠다.

완전 탐색을 사용하면 될 줄 알았는데 시간이 너무 오래 걸리기 때문에, 동적 프로그래밍을 구현해야 한다는 것을 알게 되었다.