[BOJ] 15684 사다리 조작 (C/C++)

15684번: 사다리 조작

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선	2번 세로선

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

---

상당히 오랜만에 백준 문제를 푼 느낌이다. 이번에 삼성 인턴을 넣었는데 운 좋게도 자소서를 합격했다. 그래서 중간고사끝나자마자 다시 삼성 기출로 회귀했다. 근데 못 붙을 것 같다...ㅋㅋ

 

이 문제는 그냥 단순히 구현으로만 하면 그리 어렵지 않았던 문제였다. 삼성 기출문제 중에 마법사 상어 시리즈가 있는데 얼마 전에 그 시리즈 중에 2문제를 풀어봤다. 걔네들은 아주 구현이 괴랄했다. 특히 그중 하나는 거의 0.8B형 정도는 됐었던 것 같다. B형에 비하면 시간 복잡도를 생각하지 않아도 되긴 하지만 그래도 쉽지 않았다...

 

이 문제는 가로 사다리를 2차원 배열에 표현해서 풀 수 있었다. 2번째, 3번째 세로 선 사이에 3번째 가로선이 있는 경우엔 배열의 [2][3]을 set 했다. 그리고 DFS + 완전 탐색으로 풀었다. 우선 현재 사다리가 정답이 될 수 있는 지를 검사하고 사다리를 하나 추가해서 DFS를 depth가 3까지 돌린다. 

 

처음에 풀었을 때는 800ms? 정도 시간이 나왔다. 더 시간을 줄일 수 있는 방법이 없을까 해서 구글링을 조금 해봤다. 그랬더니 무려 0ms짜리 코드도 있었다. 그 코드는 처음부터 depth를 3까지 검사하는 게 아니라 0부터 3까지 하나하나씩 검사하는게 핵심이었다. 따라서 depth를 올려가면서 중간에 정답이 있으면 프로그램을 종료한다. 그런데 나는 이 방법을 쓰게 되면 답이 1~2일 때는 좋지만 3인 경우엔 똑같은 작업을 더 많이 반복하게 될 것 같다고 생각했다. 그런데 결과를 보면 그렇지 않은가 보다. 이 아이디어를 채택해서 내 코드도 수정했다.

 

 

후기)

9%에 어떤 테스트 케이스가 숨겨져 있길래 시간이 오래 걸릴까..?