BOJ 17971 - Ladder Game

혼자 사다리타기에 대한 다양한 방법으로 연구하며 시간을 보내다 만난 문제이다.

오랜 시간 연구했던 탓인지 상대적으로 쉽게 해결할 수 있었다.

 

사다리들이 배치되어 있고 꼭 필요한 사다리들만 출력하는 문제이다.

 

문제를 해결하기 앞서 사다리타기의 성질을 알아보자. 세로줄 사이에 사다리를 하나 놓으면 a,b는 서로 swap이 된다. 그렇다면 여기서 할 수 있는 발상은 매우 단순하다. 한번 이미 사다리를 타고 이동했을때의 모든 도착지점을 안다고 생각해보자. i번째 출발점에서 도착점으로 가기 위해서는 그 거리만큼 사다리가 필요하다. 여기서 중복되는 사다리들이 존재할 수 있는데 여기서는 교차점이라고 말하겠다. n개의 출발점에서 도착지점으로 이동하는 모습을 표현하면 결국 사다리는 중복됨으로 교차점이 발생하는 구간에서 사다리를 하나 아낄 수 있다.

두 구간에서 교환이 일어나는 모습이다.

여기서 더 원초적으로 보면 처음에 말했듯이 사다리 하나는 두 값의 위치를 바꾸는 역할을 한다. 하나의 구간에서 사다리가 여러개 생기면 다시 반대편으로 돌아가는 현상이 나타나고 비효율적이다. 가는 방향이 다르면서 그 경로가 겹치는 경우에는 하나의 사다리로 두 경로에 간섭이 일어나지 않게끔 할 수 있는 것이다. 결국 하나의 원하는 순열을 만들기 위해서 필요한 swap횟수는 버블소트를 했을때 생기는 횟수와 같다. 이제 문제를 해결하는데 필요한 코드만 구현하면 된다! 버블소트의 swap횟수가 필요한 사다리의 개수라면 문제를 금방 해결할 수 있다.