[diamond5][해설안봄, 분류확인] 10060 감시 카메라 (분류 알고리즘과 다르게 품)

https://www.acmicpc.net/problem/10060

 

오랜만에 푼 다이아몬드 문제이다. 

 이 문제를 보고 scc 사이클 문제처럼 풀어야 겠다는 아이디어를 떠올리기 까지는 그렇게 어렵진 않았지만, 구체적인 방향성이 잘못되어서 수많은 반례로 고통받다가 방법을 바꿔서 겨우 맞췄다. 

 그 후 또 한가지 풀이법이 떠올랐는데 이 방법이 더 깔끔할 것 같았지만 처음 아이디어로 풀어보기로 했다.  분류로 희소배열(sparse table)이 되어있는데, 두번째 떠올린 아이디어와 일치하는 분류인 것 같다. 더 깔끔할 것 같지만 희소배열은 아이디어만 알고 있고 문제는 아직 안풀어봐서,  선뜻 내키지 않았다. (분류 확인한 건 세그먼트 트리면 거르려고...) 

 

사이클 문제로 풀기 위해서 가장 중요한 첫번째 과정은 감시 범위가 다른 카메라에 비해 열등한 카메라를 우선 제거하는 것이다.

 

a(감시범위의 왼쪽)을 기준으로 정렬한 후 (a가 같다면 b(감시범위의 오른쪽)의 오름차순으로 정렬)  한 카메라가 다른카메라보다 a가 크고 b가 작다면 그 카메라를 제거한다.

그런데 어려운 포인트는 원순열이므로, 한 바퀴를 돌았을 때를 고려해야 한다. 

원임을 고려할 때 나같은 경우는  N = 100 일때  [98,3]  , [5.4] 와 같은 경우, [98,103] , [5,104] 처럼 한바퀴를 넘겨서 돈 것으로 가정해 범위를 수정하였다.

입력이 왼쪽일때  오른쪽과 같이 정렬하였다.

 

그럼 이제 이 정렬에서 매우 중요한 점은     카메라1  a > 카메라2 a 이면  카메라1 b > 카메라2 b 라는 점이다.

이 점을 이용하면 사이클을 형성할 수 있다.

검정색 범위의 카메라가 있을 때 파란 범위의 카메라 3개중 선택할 카메라는  a 가  검정카메라 b보다 작은 카메라 중 a가 가장큰 카메라이다.  

 우리는 카메라 개수를 최소한 으로 하면서 범위 전체를 덮는 것이다. 여기서 매우 중요한 점은  정답을 이루는 카메라들에 카메라1이 포함되어 있다면,  카메라 4 도 무조건 정답에 포함된다는 것이다. 

안 덮이는 구간을 만들지 않고 카메라 1 다음의 카메라를 선택하는 것은 당연히 카메라 4가 될거기 때문이다.

즉 사이클에서 카메라1을 방문하게 된다면 다음 카메라는 무조건 카메라4.

 

이 점을 유의하며 처음 구현하려 했던 방법을 설명해 보겠다.

 

 

시작포인트를 1번으로 하면, 카메라는 1 ~10번 까지 돌다가 시작카메라와 범위가 겹치면 하나의 사이클이 만들어 질 것이다.

 

이제  , 더 왼쪽으로 가서 10번카메라를 시작점으로 둔다.

4번까지 갔을 때, 5번 카메라 부터는 기존에 돈 파란색 사이클에 포함이 된다는 것을 볼 수 있다. 그런데 아까 확인한 중요한 사실대로 라면, 5번을 선택하면 무조건 6번, 7번,8번,9번,10번을 선택하게 된다. 따라서 5번부터는 더이상 사이클을 돌 필요가 없다.

따라서 시작지점을 반시계로 하나씩 옮기면서 시계방향으로 순환할때 이미 방문한 카메라가 다음순서라면 더이상 순회를 하지 않아도 된다. (단 , 파란색에서 10번인 카메라가 빨간색에선 1번이 되므로, 시작지점은 방문에서 제외한다.) 그 후 사이클의 시작카메라를 파란색기준 1번에서 빨간색 기준 1번으로 변경한다.  왜냐하면 두 사이클은 모두 5번부터는 같은 여정을 공유하는데, 시작지점은 빨간색1번이 파란1번보다 더 왼쪽이므로,  전체 카메라 개수가 줄어들 여지가 있기 때문이다.

 

 

그 다음은 초록으로 2번째에서 이미  빨간색 사이클에서 방문한 카메라이다. (초록1번도 파란색에서 방문하긴 했지만 시작지점은 방문에서 제외하기로 했으므로, 초록 1번은 방문확인에서 제외) . 그러나 같은 카메라인데 초록에선 2번째이고 빨강에선 첫번째이다. 이런 경우는 시작카메라를 초록1번으로 업데이트 하지않고 순회를 종료한다. 

A사이클이 B사이클보다 유리한 경우는 A사이클이 B사이클의 카메라 k를 방문했을 때, A사이클의 시작점이 B사이클보다 왼쪽이고,

시작점부터 k까지의 카메라 갯수가 같은 경우이기 때문이다. (적은 경우는 존재하지 않는다 . 잘 생각해보면 알 수 있다)

그러나 같은 카메라에서 count가 크면, 유리하지 않게 된다.

 

저 사진에서 초록1번 -> 초록2번은 사실 파랑 9번 -> 파랑10번이기 때문이다. 그래서 count가 더 큰경우는 이미 다른 사이클에서 방문한 경우이다.

 

즉 이방법은 시작점을 점차 시계반대방향으로 옮기면서 사이클을 돌때 이미 방문한 카메라고, count 가 같은 경우라면 그 사이클의 시작점을 업데이트 하는 방식이다.

 

그러나 이 방법은 구현도 복잡할 뿐만 아니라, 수많은 반례가 존재하였다.........

위와 같은 경우 파란색부분 부터 시작한다고 하자. 파란색 사이클은 검정 카메라를 포함시키게 된다.

그리고 계속 시작점을 시계반대방향으로 이동하다가 빨간색 카메라의 차례가 왔다고 치자. 빨간 색 카메라도 사이클을 돌며 검정카메라을 포함하게 되고, 

아까의 논리대로라면 시작점이 더 시계반대방향일 때, 같은 카메라를 방문하게 되면 무조건 그 시작점으로 업데이트를 해야한다.

그러나 위의 경우, 빨간색 카메라로 시작점을 설정하게 되면, 결과적으로 파란카메라보다 불리하게 된다.

즉 시작점을 파란색부터 시작해, 시계반대로 옮겨가게 되면 초록색 카메라를 시작으로 하면 기존 논리에 정합하나, 한바퀴 돌아 빨간색에 도달하게 되면 논리에 맞지 않게 된다.  

 이 부분을 해결하려면 할수는 있지만 원순열이고 수많은 케이스들이 존재하기 때문에 더 이상 정신적 고통을 받고 싶지 않아 다른 아이디어를 생각하게 되었다. 

 이 아이디어가 문제가 되는 근원은 지금까지 사이클은  시계방향으로 이어나가는 방향이었는데 , 저 방법은 시작점을 시계반대방향으로 돈다는 것이다. 사이클을 돈다는 것은  b (경계선 오른쪽)에  a가 가장 가까운 카메라를 기준으로 시계방향으로 이어나가는 것인데 시작점을 재설정하는것은 시계반대방향이므로, 정합성에 어긋나는 것 같다.

  수많은 반례를 무릅쓰고  아이디어를  구현하려면 구현할 수는 있지만 매우 더러워지고 추잡해지는... 그런 풀이고 새로 생각한 아이디어가 정석적이고 깔끔한 것 같다.

 

 

이 방법은 구현도 훨씬 간단하고 정합하다.

이 방법은 시작 카메라를 선택했을 때, 그 카메라가 정답에 포함되면 그 카메라를 연결하는 다음 카메라들도 모두 정답 카메라들이라는 것에 기반한다. (밑에서 1번이 정답에 포함된다면, 2~10번도 모두 정답에 포함)

그런데 시작 카메라가 정답에 포함되지 않을 수도 있다. 이 경우는 어떻게 알 수 있을 까? 아래의 예시를 봐보자

 

 

우선 처음에는 시작카메라를 1번으로  설정하고 사이클을 한 번 돈다. 이때까지의 사이클(파란색)의 이름은 1이다.  또한 사이클1의 시작점은 1번카메라로 둔다.

 

10번까지 돌았을 때, 만약 1번 카메라가 정답에 포함되었다면, 10번 다음의 카메라는 1번이 될 것이다. 

그러나  10번 다음의 카메라는 1번이 아니다.

10번다음의 카메라는 1'  이다! 이러한 일이 발생하는 이유는 시작카메라를 설정했을 때 , 그 다음에 오는 카메라들은 정해졌지만, 그 시작카메라가 정답이 아닐 수도 있기 때문이다. 

따라서 사이클1의 시작점을 1번에서 1' 로 변경한다.  

시작카메라의 b(범위의 오른쪽)이  카메라1보다 카메라1' 이 더 오른쪽이므로 무조건 이득이다. 

그 후 1' , 2' , 3', 4' 을 차례로 돈다. 다음카메라 6번은 이미 방문하였으므로, 순회를 종료한다. 또한, 

새로운 시작점을 새로 업데이트한 사이클은 1' -> 2' -> 3' -> 4' -> 6 번인데, 기존의 1->2->3->4->5->6 보다 카메라를 하나 더 줄였다.  6번을 마주쳤을 때 종료하는 이유는 아까 처럼 6번부터는 그 뒤의 사이클(6->7-->8->9->10)이 정해져있기 때문이다.

 결과적으로 사이클1의 시작점은 1' 이 된다.  findRoot[1] = 1'  로 시작점을 저장한다.

즉  시작 카메라를 업데이트 해나가며 계속 돌다가 이미 방문한 카메라를 만나게 되면, 그 사이클의 시작점은 최종적으로 업데이트한 시작점이다.

 

만약 위 처럼 새로운 시작점으로 1' ->2' -> ... 8' 까지 돌고 그 다음 카메라가 1'이 아닌 1'' 이라면  사이클1의 시작점은 1'' 이 된다.

 

이런식으로 사이클1의 시작점을 구하게 되었고, 

그다음 사이클2는 지금까지 돌았을 때 방문하지 않은 카메라를 시작점으로 돌면 된다. 그러다가  사이클1에서 방문했던 곳을 방문하게 되면 바로 종료하면 된다. 

위처럼 사이클2 (빨간색)을 돌다가 4' 카메라를 만났을 경우, 종료하게 된다. 그 이유는 이미 4'를 포함하는 사이클1에서 최적의 시작점은 1'' 으로 정리가 되었는데 어정쩡한 녀석(사이클2)의 시작점은 상대도 안되기 때문이다.

따라서 이미 방문된 카메라 부터는 다시 순회를 안하게 되므로, 

이 알고리즘 시간복잡도는 NlogN이 된다. (logN 은 이분탐색  or treeSet으로 카메라의 b이하의 가장 큰 a를 가지는 다음 카메라를 탐색하는 복잡도).

대부분의 분들이 희소배열로 푸셨는데 다른 방법으로 동고쇼해서 풀었다는 걸 깨닫고 나니 재밌었다

나름 정석적인 풀이 같았는데...