[기타] 라인 스윕

 

그림. 1

위처럼 위치가 표시되어이있는 직선에 임의의 점 2개를 찍고 직선을 긋는다.

 

직선끼리 일부분이 겹칠 수도 있다.

 

총 N개의 직선을 그었을 때 그어진 선의 전체 길이를 구하는 문제이다.

 

 

 

 

간단하게 직선마다 배열에 1을 찍으며 길이를 구할 수도 있지만 그렇게 하면 

 

선분의 수가 많아졌을 때 매우 비효율적인 알고리즘이 되어버린다.

 

극단적인 예를 들었을 때 위 문제의 최대 데이터가 +-10,0000이고 길이 최대인 선분 1,0000개를 그린다고 하면 

 

총 20,0000,0000번 반복하는 알고리즘이 되어버리는 것이다.

 

위 문제는 대부분 주어지는 N과 전체 구간의 크기가 크기 때문에 O(n) 복잡도를 가지도록 구현 해야한다.

 

 

 

 

a.  기본 개념 풀이

 

     직선의 양 끝단을 받을 때 a가 b보다 작다면 a와 b를 바꿔 저장한다.

 

     즉 배열에 넣을 때 arr[j][0]에는 직선의 시작점이, arr[j][1]에는 직선의 끝점이 들어가도록 입력을 받는다.

 

     이후, 모든 배열을 시작점을 기준으로 정렬을 해준다. 

 

     배열의 끝까지 나가며 다음을 작업을 실행한다.

         0. 현재 시작점 a, 현재 끝점 b를 초기값으로 설정

         1. 배열에 들어있는 다음 시작점 x를 꺼내 a와 b의 사이에 있는지 검사.

             1-2. 사이에 있을 경우 x와 대응하는 끝점 y를 불러와 b보다 뒤에 있으면 현재 끝점 b를 갱신

                   앞에 있을 경우 검사를 종료하고 다음 시작점을 불러온다.(해당 선은 현재 선에 포함되어있음)

             1-3. 사이에 없을 경우 a, b의 차이를 sum에 더하고 a와 b를 x 와 y로 갱신

 

     선분을 시작점 순으로 정렬하고 다음 선분이

             1.현재 선분에 포함되는지

             2.걸쳐있는지

             3.독립적인 직선인지

     3가지 조건을 검사하여 최종 길이를 구한다.

 

 

위의 알고리즘의 문제점은 직선의 갯수가 많아질수록 시작점을 기준으로 정렬하는 과정이 시간을 많이 먹는다는 것이다.

 

b. 메모리를 더 사용하여 시간 단축

 

    기본 원리는 a에서 사용한 방법과 동일하다. 대신 직선 양끝점을 배열에 할당하여 정렬 과정을 생략한다.

    최대 선분길이가 M이라고 했을 때 크기 2M짜리 배열을 할당 받고

    a, b를 입력을 받아 arr[a + M] = b + M 식으로 저장을 한다.

    현재 선분 끝점을 저장할 변수 c = 0를 선언하고 전체 선분(2M)에 대해 다음 작업을 실행한다.

       1. 값이 들어있는 arr 번지를 찾는다.

       2. 해당 번지가 c보다 큰지 검사한다.

         크다면 새로운 점이 독립적인 직선의 시작점이므로 새로운 직선의 길이를 sum에 더한다.

         작다면 새로운 시작점이 현재 직선에 포함된 경우이다. 원래 끝점과 c의 차이를 sum에 더하고 c를 현재 끝점으로 갱신한다. 

 

 

위의 방법을 사용하면 굳이 시작점을 기준으로 정렬을 할 필요가 없다.

구조는 a와 완전히 동일하므로 따로 설명하지 않겠다.

 

실제 코드::

#include <stdio.h>

int arr[1000][1000];
int n;
int dot[1000][2];
int line[2000005];

int main() {
	int n;
	int i, j;
	int a, b;
	scanf("%d", &n);
	for (i=1;i<=n;i++) {
		scanf("%d %d", &a, &b);
		if(a > b) {
			int t = a;
			a = b;
			b = t;
		}
		line[a + 1000000] = b + 1000000;
	}
	
	int sum = 0;
	int current;
	for(j=1;j<=2000000;j++) {
		if(line[j] != 0) {	
			if(current <= j) {								
				sum += line[j] - j;
				current = line[j];
			}
			else {
				if(line[j] < current) continue;
				sum += line[j] - current;
				current = line[j];					
			}			
		}
	}

	printf("%d\n", sum);
	
	return 0;
}