Baekjoon(백준) 14865번 - 곡선 자르기

백준 사이트의 14865번.
문제 제목 : 곡선 자르기
백준 14865

한국정보올림피아드 (KOI) 2017년도 중등부 2번 문제이다.
그렇게 오래 안 걸릴 문제였는데 중간에 바쁜 일이 많아서 문제 풀이 흐름이 자꾸 끊긴데다 골치 아픈 버그 때문에 코드가 자꾸 안 돌아가서 디버깅에 시간이 좀 걸렸다. 원래 디버깅해서 겨우 성공시키고 나면 골치 아프게 했던 버그가 별거 아닌 경우가 대다수인데 이번 경우는 더더욱 어이가 없어서 현타가 왔었다.

문제 해석

이 문제는 문제 해석부터가 좀 중요하다. 문제를 처음보면 이거 뭐 기하적으로 해석해서 풀어야되나 라고 생각할 수 있는데 그렇게 복잡하게 생각할 필요가 없다. 문제를 간단하게 바꿔서 해석하는 능력이 중요한 것 같다. 문제는 간략하게 얘기하면 2차원 좌표 평면에 수평 선분과 수직 선분이 한 번씩 번갈아가며 이어진 경계선을 가진 직교다각형이 주어지고 여기서 $y = 0$ 을 기준으로 밑을 지워내면 위에만 남는데 여기서 ‘봉우리’들을 보겠다는 것이다.

봉우리는 시작점과 끝점이 $x$축 상에 있는 곡선 부분과 $x$축으로 둘러싸인 영역을 말한다.

이 때 다른 봉우리에 의해 포함되지 않는 봉우리 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 각각 출력하면 된다. 근데 이 직교다각형에 조건이 붙어있는데 이를 정리하면 다음과 같다.

1. 시작점과 끝점이 붙어있다.
2. 그 이외에는 선이 교차하거나 붙는 경우는 없다.
3. 수평 선분과 수직 선분이 한 번씩 번갈아가며 이어진 경계선
4. 모든 꼭짓점은 서로 다르며, 연속한 두 변 이외에는 어떤 두 변도 만나지 않는다.
5. 주어지는 꼭짓점들은 각 수평 선분 또는 수직 선분의 양 끝이며 그 꼭짓점들 순서의 방향은 가장 왼쪽에 있는 수직 선분인 변을 볼 때 아래에서 위로 올라가는 방향이다. (근데 이게 지금 소개하는 풀이에서는 중요한 조건은 아닌 것 같다)
6. 꼭짓점 $y$좌표가 0인 경우는 없다.
7. $x$축과 교차하는 변이 반드시 하나 이상 존재

조건이 많은데 문제를 풀 때 방해가 되는 귀찮은 요소들을 거의 다 제거해준 것이라 보면 된다. 이러한 조건 하에서 우리는 봉우리를 ‘범위’로 생각할 수 있다. 예를 들어 이런 직교다각형을 생각해보자.

여기서는 봉우리를 범위(왼쪽 끝과 오른쪽 끝의 $x$좌표)로

봉우리	left	right
1	-4	3
2	-2	-1
3	-1	1

이렇게 데이터화 할 수 있다. 이 각각의 봉우리들은 pair 나 struct 를 사용해서 저장하면 편리할 것이다. 나는 struct를 사용했다. 설명을 길게 했는데 핵심은

봉우리들을 범위로 표현해서 데이터화

한다는 것이다.

풀이 전략

이 문제는 스택(stack)을 활용해서 풀었다. 나는 그냥 이 방법이 바로 떠올랐는데 사실 그러기는 쉽지 않다. 꽤 독특하고 깔끔한 알고리즘인 것 같아서 이 방법으로 소개한다.
봉우리들을 모두 앞에서 말한것처럼 데이터화 했다면 봉우리의 왼쪽 좌표 기준으로 오름차순으로 정렬한다. 이 후 봉우리들을 모두 앞에서부터 스캔하면서 stack을 이용해서 답을 구한다.

stack은 봉우리들의 포함관계를 나타내도록 한다.

말 그대로이다. 지금 현재 스캔하는 봉우리를 기준으로 그 봉우리를 포함하는 가장 작은 봉우리 (가장 하위의 봉우리) 가 stack의 top이 되고, 또 stack의 top 봉우리를 포함하는 가장 작은 봉우리가 top - 1에 있는 봉우리… 이런 식으로 되는 것이다.
그러면 잘 생각해보면 이 stack을 이용해서 ‘다른 봉우리에 의해 포함되지 않는 봉우리 개수’ 이거나 ‘다른 봉우리를 포함하지 않는 봉우리 개수’ 인 것을 판단하고 문제에서 원하는 대로 그것들을 카운팅할 수 있다.

다른 봉우리에 의해 포함되지 않는 봉우리 : 스택이 empty 할 때

다른 봉우리를 포함하지 않는 봉우리 : 현재 봉우리가 스택의 top에 ‘포함’되지 않을 때

구현

1. 봉우리 파악

일단 봉우리를 데이터화 해야 한다. 우리에게 입력으로 주어지는 것은 꼭짓점의 좌표이다. 꼭짓점이 주어지는 순서는 직교다각형에서 일정한 방향으로 돌아가는 순서이지만, 주어지는 첫 꼭짓점은 $y>0$ 에 있을 수도 있고 $y<0$에 있을 수도 있다. vector에는 rotate 인가? 뭐 그런 함수도 있어서 그걸 이용하면 되는 것 같긴 한데 난 그걸 잘 모른다. 그래서 그냥 $y<0$에서 시작하는 것으로 기준을 정하고 $y<0$ 영역에 있는 꼭짓점의 index를 아래 코드와 같이 찾아주었다.

int idx;
idx = 0;
if(input_seq[0][1] > 0) {
	idx = N - 1;
	while(input_seq[idx][1] > 0) {
		idx--;	
	}
}

문제는 그렇게 되면 꼭짓점을 스캔할 때 처음 시작점이 index 가 0이 아니고 따라서 (N+1)개의 index를 차례로 스캔하면서 index 가 N이상이 되면 0으로 바꾸어주는 것이 필요하다. 왜 근데 (N+1)개의 index를 스캔할까? 마지막 모서리가 $x$축과 교차할 수 있기 때문에 마지막 꼭짓점은 다시 처음의 꼭짓점을 한 번 더 스캔해야 한다. 물론 while 문 안에 if 문 넣어서 구현할수도 있겠지만 깔끔하게 ‘나머지’를 이용했다. for문의 index가 i 라면 실제로 for 문 안에서 이용하는 index는 i % n 으로 하면 되는 것이다. 이후에는 꼭짓점이 $y<0$에서 다음 꼭짓점이 $y>0$으로 변한 후 $y>0$에서 $y<0$으로 변하면 그 순간을 포착하여 한 봉우리 양쪽의 좌표를 저장해주면 되는 것이다. 봉우리 양쪽 좌표 중 왼쪽 좌표는 두 좌표 중 작은 값, 오른쪽 좌표는 두 좌표 중 큰 값으로 저장해야 한다는 것을 유의해야 한다. 이 부분이 상당히 코드가 지저분하기 때문에 좀 주의해서 구현할 필요가 있다. 나는 계속 있던 골치 아픈 버그가 다음 부분에서 설명할 부분에 있는 줄 알았는데, 알고보니 이 과정에서 있었다.

2. stack을 활용해서 답 구하기

봉우리를 데이터화 해서 저장했으면 봉우리들을 각 봉우리의 왼쪽 좌표 기준으로 오름차순 정렬해야 한다. 이후 알고리즘은 앞의 풀이전략에서 설명한 것과 거의 비슷하다. 봉우리들을 왼쪽부터 스캔하면서 다음과 같이 처리한다. (ans1 : 다른 봉우리에 의해 포함되지 않는 봉우리 개수, ans2 : 다른 봉우리르 포함하지 않는 봉우리)

1. 스택이 empty하면 현재 봉우리 stack에 push, ans1++
2. 스택의 top이 현재 봉우리를 포함하면 현재 봉우리 stack에 push
3. 스택의 top이 현재 봉우리를 포함하지 않으면 ans2++, top이 현재 봉우리를 포함할 때까지 pop, pop하는 과정에서 empty가 되면 ans1++ 하고 break, 이후 현재 봉우리 추가

직접 머릿속으로 시뮬레이션 해보면 알겠지만 마지막 봉우리에 대해서는 ans2가 카운팅되지 않기 때문에 ans1의 초기값은 0, ans2의 초기값은 1로 설정하고 봉우리 전체를 스캔하면서 카운팅할 필요가 있다. 다음 사진은 위의 알고리즘을 예시에 적용한 것이다. 가장 위에 있는 것이 봉우리들의 예시이고, 봉우리 각각을 숫자로 표현하여 스택에 push, pop 되는 것과 ans1, ans2가 어디서 더해지는지 보여준다.

또한, 이 전체 코드를 통틀어서 variable이 integer 범위를 넘는 경우가 있을 수 있다. 혹시나를 위해서 그런 가능성이 있는 variable은 long long int 형태로 선언해주는 것이 좋다. (사실은 범위를 넘는 경우가 있는 것 같다)
솔루션 코드는 github에 있다.

baekjoon 14865 solution code