구름톤 챌린지 4주차 - 3번

18일차 - 중첩 점

---

문제 내용

• 한 변의 길이가 N인 정사각형 위에 M개의 반직선을 그립니다.

1. 반직선을 그릴 칸(y,x)를 구합니다.(주어진 정사각형을 1x1의 정사각형으로 나눌 때 y번째 행, x번째 열에 해당하는 칸)
2. 반직선을 그릴 방향(d)을 정합니다. 방향은 상하좌우(UDRL)로 구별됩니다.
3. 반직선을 그립니다. 반직선은 해당 칸의 테두리에서 시작되며, 다른 평행한 반직선과 겹치지 않습니다.

• 이 때, 반직선과 반직선이 겹치는 중첩 점의 개수를 구해야 합니다.

해결 방법

• 수직으로 지나는 직선의 개수 * 수평으로 지나는 직선의 개수 = 중첩 점의 개수 임을 이용합니다.
• 수직으로 지나는 직선의 개수를 담은 배열과 수평으로 지나는 직선의 개수를 담은 배열을 사용하여 이를 구했습니다.

주의 사항

• 중첩 점을 구하는 과정에서 두 수를 곱하게 되는데, 이 과정에서 오버플로우가 발생할 수 있으므로 곱한 값은 long long int 변수로 저장해줍시다.

작성 코드

#include <iostream>
#define MAX 100
using namespace std;

int verMap[MAX][MAX] = {0,}; // 수직선 개수 담은 배열
int horMap[MAX][MAX] = {0,}; // 수평선 개수 담은 배열

struct point {
	int x;
	int y;
};

struct point getPos (int x, int y) {
	struct point p;
	p.x = x;
	p.y = y;
	return p;
}
void draw(char c, struct point p, int n) { // 선 긋기
	if(c == 'R')
		while(p.x < n)
			horMap[p.y][p.x++]++;
	else if(c == 'L')
		while(p.x >= 0)
			horMap[p.y][p.x--]++;
	else if(c == 'U')
		while(p.y >= 0)
			verMap[p.y--][p.x]++;
	else
		while(p.y < n)
			verMap[p.y++][p.x]++;
}
int main() {
	int n, m;
	int a,b;
	char c;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		draw(c,getPos(b - 1, a - 1),n); // 해당 방향으로 선 그음
	}
	long long int sum = 0; // 오버플로우 방지
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			sum += (long long int)verMap[i][j] * horMap[i][j]; // 두 수를 곱하는 과정에서 오버플로우 발생 가능성 있음
	cout << sum << endl;
}

소감

• 코드를 짜는 건 어렵지 않았지만, 오버플로우 문제를 발견하는데 오랜 시간이 걸렸습니다.
• 오버플로우를 항상 조심해야된다는 것을 상기시키는 좋은 기회였습니다.