[구름톤 챌린지] 중첩 점 (C++)

문제

한 변의 길이가 N인 정사각형이 있다. 이 정사각형 위에 M개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세기

생각할 것

• 평행하지 않은 반직선만 중첩된다는 점을 이용하기.
• 처음에는 지나가는 위치에 모든 방향을 push_back으로 기록했다. 그랬더니 일부 테스트 케이스에서 시간 초과가 발생했다.
  • 이를 개선하기위해 해당 위치를 지나는 점에 대해 방향의 개수만 더해주기로 했다.
• 마지막 테스트 케이스 하나가 틀렸다. ㅠㅠ
  • 결과의 개수를 더할 때 오버플로우가 발생하는 문제였다.
  • res 변수의 타입을 long long으로 바꿔주었더니 정답. 항상 주의하기!

코드

#include <iostream>
#include <vector>
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
	int N, M;
	long long res = 0;
	
	cin >> N >> M;
	vector<vector<vector<int>>> board(N, vector<vector<int>>(N, vector<int>(4))); // 해당 위치를 지나가는 선의 방향 개수를 기록

	int x, y; char d;
	for(int i=0; i < M; i++){
		// 점 입력
		cin >> x >> y >> d;
		x--; y--;
		
		// 방향 설정
		int dir;
		if(d == 'U') dir = 0;
		else if(d == 'D') dir = 1;
		else if(d == 'L') dir = 2;
		else if(d == 'R') dir = 3;
		
		// 선 긋기
		while(1){
			// 중첩점 체크
			if(dir == 0 || dir == 1){
				res += board[x][y][2];
				res += board[x][y][3];
			}
			else if(dir == 2 || dir == 3){
				res += board[x][y][0];
				res += board[x][y][1];
			}

			// 선 개수 더하기
			board[x][y][dir]++;
						
			// 다음 위치		
			x += dx[dir];
			y += dy[dir];
			if(x < 0 || x >= N || y < 0 || y >= N) break;
		}
	}
	
	cout << res;
	return 0;
}