Junnnho

두 선분이 주어질 때 선분이 교차하는지 판별하는 방법을 알아보겠습니다

선분 AB, CD 가 다음과 같이 있다고 가정하겠습니다

이 때 선분 AB, CD 가 교차하는지 확인하는 방법은

삼각형의 면적을 구하는 공식+벡터 를 통해서 결정할 수 있습니다

이를 구하는 함수는 보통 CCW (반시계방향의 줄임말) 으로 세점에 대한 방향성을 확인하는 함수라 칭하겠습니다

삼각형의 면적 + 벡터를 구하는 공식은 다음과 같습니다

1, 2, 3 을 각각 함수의 인자로 받게될 선분의 정점이라고 가정한다면

다음과 같은 함수를 만들 수 있습니다.

1 2 3 4 5 6 7 8 9 10

typedef struct {     int x, y; }pii;   int ccw(pii a, pii b, pii c) {     int ans = (b.x - a.x) * (c.y - a.y) - (b.y - a.y)* (c.x - a.x);     if (ans < 0) return 1;     else if (ans > 0) return -1;     else return 0; }

 

위의 그림에서 선분 AB로 선분CD를 확인하는 CCW는 다음과 같이 호출할 수 있습니다

CCW(A,B,C), CCW(A,B,D) 

CCW(A,B,C) 의 의미는 선분 AB 에 대한 정점 C 의 방향을 벡터로 반환받는다는 의미입니다

이 때 CCW(A,B,C) * CCW(A,B,D) 의 곱이 음수이면, 즉 각 함수의 반환값이 0이 아닌 음수와 양수이면

두 선분은 교차하는 것으로 판별할 수 있습니다.

만약 값이 0 이라면 두 선분은 평행하다는 의미입니다.

 

지금까지의 설명은 임의의 볼록다각형에서 사용할 수 있는 방법입니다.

다시 정의하자면, 어떤 주어진 볼록다각형의 그 선 위에 있는 좌표끼리로만 판단할 수 있다는 의미입니다.

 

다음 설명할 것은 볼록다각형이 아닌 좌표평면에 대한 두 선분의 교차를 판별하는 방법입니다.

정해진 선 위에서 존재하는 정점이 아니라면 다음과 같은 경우가 있을 수 있습니다.

선분AB 에 대해서 선분CD 에 대한 CCW 를 구하게 되면 분명 그 곱은 음수가 될 것입니다.

교차한다는 의미가 됩니다.

하지만 육안으로 보면 두 선분은 교차하지 않고 있습니다.

어떻게 교차하는지 확인할 수 있을까요?

그 방법은 두 선분에 대한 CCW를 모두 구해주는 것입니다.

선분AB 에 대한 선분CD, 선분 CD에 대한 선분 AB 이 될 것입니다.

그리고 다음과 같은 조건에 의해 두 선분이 교차한다고 할 수 있습니다.

CCW(A,B,C)*CCW(A,B,D) <=0 && CCW(C,D,A)*CCW(C,D,B) <=0

이 식에는 다음과 같은 반례가 존재합니다.

다음과 같은 경우 두선분 각각 CCW 를 구했을 때 둘다 0이라는 값을 가지게 됩니다.

이때는 위와 같은 상태인지, 아래와 같은 상태인지 알 수 없게 됩니다.

이럴 때 두 선분이 교차하는지 확인하는 방법은 정점의 상대적인 위치를 확인해주는 것입니다.

B가 C 보다 크거나 같고 A 가 D 보다 작거나 같으면 두 선분은 교차하게 됩니다.

A<=D && B>=C

BOJ : https://www.acmicpc.net/problem/16991

github : https://github.com/junho0956/Algorithm/blob/master/16991/16991/%EC%86%8C%EC%8A%A4.cpp

BOJ 외판원 순회2 https://junho0956.tistory.com/172?category=825557

위 문제를 통해 풀이한 문제입니다.

달라진 것은 소수점 표현인데,

정점이 좌표로 주어지는 방식이고, 좌표끼리의 거리를 알기 위해서

완전탐색을 통해 각 좌표사이의 거리만 구해준 후 TSP의 흐름과 똑같이 풀어주시면 됩니다

BOJ : https://www.acmicpc.net/problem/2098

github : https://github.com/junho0956/Algorithm/blob/master/2098/2098/%EC%86%8C%EC%8A%A4.cpp

BOJ 10971번 외판원 순회2 (https://junho0956.tistory.com/172)을 통해 풀이하였습니다. 

BOJ : https://www.acmicpc.net/problem/10971

github : https://github.com/junho0956/Algorithm/blob/master/10971/10971/%EC%86%8C%EC%8A%A4.cpp

TSP, 외판원 순회는

한 정점에서 모든 정점을 중복없이 방문하고 다시 첫 정점으로 되돌아오는 최단거리를 의미합니다

일반적으로 TSP를 해결하기 위해서는 정점이 N 개일때 N! 이라는 시간이 필요하게 됩니다.

이 문제에서는 정점이 최대 10개이기 때문에 10! = 3628800번의 시간복잡도가 필요하게 됩니다.

시간제한도 2초이기 때문에 완전탐색으로 10! 으로 문제를 해결할수도 있습니다

하지만 정점이 커질수록 TLE 가 될수밖에 없기 때문에 제대로된 방법을 알아보겠습니다

(2098번 외판원 순회 https://www.acmicpc.net/problem/2098 의 경우 16! = 20조이상의 시간복잡도가 필요하게됩니다)

먼저 외판원을 순회할때의 시작정점은 어떤 정점이든 상관없습니다.

방향트리를 가정하고 있기 때문에 시작정점에 따라 값이 다를 수 있다 생각할 수 있는데,

결국 최단거리인 TSP를 찾게되면 그 정점들은 사이클이 생기기 때문입니다

(ex 1 -> 2 -> 3 == 2->3->1 == 3->1->2) 

알고리즘 수업시간 때 배운 TSP에 대해서 설명해보겠습니다.

TSP는 시간복잡도를 줄이기 위해서 동적계획법에 의한 계산을 하게 됩니다

기본적인 DP의 점화식은 다음과 같습니다

위에서 시작정점은 어디든 상관없다고 말씀드렸으니, 시작정점은 1이라고 가정하고

{V} 를 방문하지 않은 정점이라고 가정하겠습니다.

"dp[i][{V} 의 의미는 정점 i 에서 출발해서 아직 방문하지 않은 정점집합V 를 거쳐 정점 1로 되돌아오는 최단거리"

를 의미하게 됩니다.

결국 dp[v1][{V-v1}] = min (2<=j<=k) (cost[1][j]+DP[j][{V-v1,vj}] 라는 점화식을 만들 수 있게 됩니다.

하지만 이 DP는 단순하게 구현하려면 엄청나게 많은 메모리가 필요하게 됩니다.

정점 1 2 3 4 5 가 있을 때

정점 1에서 출발하여 만들어볼 수 있는 DP는

1 2 3 4 5

1 2 3 5 4

1 2 4 3 5

1 2 4 5 3

1 2 5 3 4

1 2 5 4 3

1 3 . . .

이렇게 DP는 어떤 정점에서 어떤 정점을 거쳤는지에 대한 순서와 값들을 알고 있어야되는 것입니다

이걸 단순히 배열로만 다 표현하려면 엄청나게 많은 메모리가 들 수 밖에 없습니다

그렇기때문에 이 순서들을 DP로 표현하기 위해서는 비트마스킹을 이용해야 합니다

그렇게되면 좀더 수월하게 이 집합의 순서와 값들을 유지하면서 DP를 계산할 수 있습니다

풀이과정은 다음과 같습니다.

배열은 최대정점이 N일때 1<<N 의 크기가 필요하다

현재 출발하려는 정점이 start 이고, 지금까지 방문한 정점들의 순서를 비트마스킹을 이용해서 visit으로 표현한다

비트마스킹 visit이 모든정점을 방문했다면 현재 도착한 마지막 정점에서 정점1로 가는 값을 반환합니다

모든 정점을 방문하지 않았다면 현재까지 정점에 대한 DP 값을 확인합니다

만약 DP 가 초기값이 아니라면, 이는 이미 이 순서에 대한 최단거리를 가지고 있는 것이므로 반환합니다

만약 DP 가 초기값이라면, 현재 정점부터 정점1을 제외한 방문할 수 있는 모든 정점을 확인합니다

비트마스킹으로 풀이하면, 현재 방문한 값과 순서는 visit에 담겨있습니다

정점 i 를 방문했는지 확인하는 방법

-> (visit & (1<<i)) == 0 이면 방문하지않음, ==1 이면 방문함

다음 방문할 정점에 대해 지금까지 방문한 값 visit을 갱신하는 방법

-> (visit | (1<<i)