[C++] 백준 15684번 사다리 조작

15684번: 사다리 조작

백트래킹 문제.

삼성 SW 기출문제에 있어서 풀어봤는데, 구현 문제가 아니라 시뮬레이션 문제였다. (사실 거의 구현에 가깝다.)

시간 초과를 줄일 수 있는 방법이 떠오르지 않아서 게시판을 계속 봤는데

원하는 게시물이 없어서 많이 헤맸다.

그러다 한 게시물을 찾아서 탐색시, 중복을 제거하라는 것을 보고 맞출 수 있었다.

백트래킹은 중복을 줄여야 맞출 수 있다는 것을 다시 한 번 배운 문제다.

 

사실 아직도 왜 맞은지는 잘 모르겠다.

시간 복잡도를 계산했을때,

탐색하는 것은 최악의 경우 270 C 3이 될거고 이는 3,244,140이다.

여기에 사다리가 올바르게 연결이 됐는지 확인하는 탐색의 경우는 10 * 30 = 300이 될 것이다.

그렇다면 3,244,140 * 300인데, 이는 973,242,000이 된다.

 

아마도 내 생각에는 사다리가 올바르게 연결이 됐는지 확인하는 탐색에서

i번째가 하나라도 연결이 안 됐을 때 바로 return되도록 만들었는데

이 경우에서 시간이 많이 줄어드는 것 같다.

아마 i번째 사다리가 i번째로 가게되지 않는 경우가 빠르게 메서드가 return되는 것 같다.

 

문제풀이

그동안 풀어왔던 백트래킹 문제들은 1 <= N <= 8 이런식으로 N이 8보다 작거나 같았는데

이 문제는 N이 10까지 갈 수 있고, 높이는 30까지 갈 수 있다.

따라서 존재할 수 있는 가로선의 수는 (10 - 1) * 30 = 270개가 될 수 있다.

즉, 270개의 가로선 중에서 3개 내의 가로선을 추가해서 i번째 사다리가 i번째가 되게 구현하면 된다.

 

시간복잡도를 계산해보면

1. 3개의 가로선을 고르는 것은 최악의 경우, 270C3 = 3,244,140

2. 사다리가 문제에서 요구하는 경우인지 확인하는 최악의 경우, 10 * 30 = 300이다.

두 개를 곱해주면 3,244,140 * 300 = 973,242,000인데,

2에서 하나의 수직선이라도 자기 자신의 번호로 가지 않는다면 return하도록 구현한다면

시간이 많이 줄어드는 것 같다.

(시간이 대체로 500ms가 나오는 걸로 봐서는 300 ->평균 16으로 줄어드는 것 같다.)

 

그러면, 사다리는 어떻게 구현할 수 있을까?

나같은 경우는 3차원 배열을 사용하기로 생각했다.

arr[31][11][2] 의 크기로 만들어놓았다.

• [31]은 높이를 의미한다.
• [11]은 수직선의 번호를 의미한다.
• [2]에서는, [0]은 앞 번호와 연결된 것을, [1]은 뒷 번호와 연결된 것을 의미한다.

예를들어, 8번째 높이에서 1과 2가 연결된 경우

arr[8][1][1] = true;

arr[8][2][0] = true;

로 선언해주겠다고 생각했다.

 

특정 높이 j에서 수직선 i에 가로선이 이미 존재하는지는

( arr[j][i][0] || arr[j][i][1] ) 이 조건을 참고하면 되도록 만들었다.

해당 높이에 해당 수직선에 앞 번호와 연결됐는지, 뒷 번호와 연결됐는지를 확인하는 것이다.

 

이런 식으로 구상한 후에, 코드를 짰다.

나머지는 코드를 보면서 살펴보자.

 

사용한 STL과 변수

STL은 따로 사용하지 않았다.

• verticalLines, horizontalLines, maxHorizontal : 순서대로 입력받는 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H이다.
• isConnected 3차원 배열 : 위에서 설명했듯이 순서대로 높이 / 세로선의 번호 / 0 : 앞번호와 연결, 1 : 뒤번호와 연결을 나타내는 배열이다.
• ans : 결과로 출력해주는 최소로 생성해야하는 가로선의 개수이다. 4로 초기화해서, 4인 경우 불가능하다는 의미로 -1을 출력하도록 만들었다.

 

메인함수

처음에 N, M, H를 입력받은 후에, M개만큼 가로선을 입력받는다.

 

M개의 가로선은 다음과 같이 입력된다.

높이a와 번호 b가 주어지는데,

a높이의 b와 b+1을 연결시켜준다는 의미이다.

따라서 내 풀이에서는

isConnected[a][b][1] // b의 뒷번호와 연결됐음.

isConnected[a][b + 1][0] // b + 1의 앞번호와 연결됐음.

이라고 저장해주면 된다.

 

그리고 go(0, 1, 1) 백트래킹 메서드를 시작하면 된다.

해당 메서드는 뒤에 나올텐데,

첫번째 매개변수가 몇 번째 가로선을 추가했는지,

두번째 매개변수는 어느 수직선 번호에서 시작하는지,

세번째 매개변수는 어느 높이에서 시작하는지이다.

두 세번째 매개변수를 추가해줌으로써, 이미 고려했던 수직선 번호와, 높이의 중복탐색을 제거해준다.

이 부분을 고려하지 못해서 자꾸 시간초과가 났었다.

 

go메서드로 백트래킹이 종료된 후에, 

ans값이 4라는 것은 값을 찾지 못했다는 뜻이다. -1을 출력한다.

ans값이 4가 아니라면 갱신된 ans값을 출력한다.

 

특정 수직선 번호(point)가 특정 높이(height)에 이미 연결된 가로선이 있는지 여부를 확인하는 메서드

특정 수직선 번호가 특정 높이에 이미 가로선이 연결되어 있는지 여부를 확인하는 메서드이다.

isConnected[높이][번호][0]이 true라면 해당 높이에서 앞 번호와 연결됐다는 뜻이고,

isConnected[높이][번호][1]이 true라면 해당 높이에서 뒷 번호와 연결됐다는 뜻이다.

 

현재 사다리의 상태가 문제에서 요구하는 조건의 사다리인지 확인하는 메서드

i번부터 N번까지 고려해준다.

curPoint를 i번으로 초기화하고 높이를 1에서 H까지 고려해준다.

해당 높이에서 앞 번호와 연결되어 있다면 앞 번호로 curPoint를 갱신하고,

해당 높이에서 뒷 번호와 연결되어 있다면 뒷 번호로 curPoint를 갱신한다.

높이 H까지 내려온 후에 만일 curPoint가 i와 다르다면,

문제에서 요구하는 사다리가 아니므로 return false를 해준다.

모든 i번까지 고려했을 때 return false되지 않았다면 return true해준다. 이는 문제가 요구하는 사다리가 됐다는 뜻이다.

 

백트래킹 메서드 - 1

백트래킹 메서드의 매개변수는 다음과 같다.

• idx : 현재 몇번째까지 가로선을 추가했는지,
• startVerticalNum : 이전 go 메서드에서 어디까지 수직선의 번호를 탐색했는지,
• startHorizontalHeight : 이전 go 메서드에서 어디까지 가로선의 높이를 탐색했는지,

백트래킹의 기초는 다시한번 말하지만 중복을 제거하는 것이다. 꼭 머리속에 새겨야 될 것 같다...

시간초과가 여러번 났었는데, 계속 (1, 1)에서 시작했어서 같은 가로선을 여러번 고려해줘서 틀렸었다.

 

맨 처음 메서드에 진입하면, idx가 현재 저장중인 ans와 비교하는 연산을 해서 idx가 더 크다면 return한다.

필수적인 부분은 아니지만, 가지치기를 한 것이다. 시간이 약 40ms정도 줄어드는데,

다른 문제들에서는 이 부분이 엄청난 차이를 가져올 수 있다.

 

그리고 위에서 작성한 사다리가 문제에서 요구하는 사다리인지를 확인하는 findCanAns()메서드로 확인해본다.

만일 사다리가 문제의 조건과 부합하는 사다리라면 ans값을 갱신한다.

그리고 return하는데, 조건에 부합하는 사다리에서 더 가로선을 배치해줄 필요가 없기 때문이다.

 

findCansAns()가 false이고, idx(현재 임의로 설치한 가로선의 수)가 3이라면 return한다. 4개까지 설치할 필요는 없다.

 

그리고 매개변수로 변수를 만들어준다. 이는 백트래킹을 할 때, 반복문을 돌리기 위함이다.

vertical = startVerticalNum 으로 시작하는 수직선의 번호를 초기화 해준다.

horizontalHeight = startHorizontalHeight 로 시작하는 가로선의 높이를 초기화 해준다.

그리고 뒤에 나오지만, 매개변수인 startHorizontalHeight는

이전 go()메서드에서 가로선을 넣은 높이에 +1을 해준 값이다.

이 값이 최대높이를 넘지 않았는지 확인해준다.

 

백트래킹 메서드 - 2

그리고 vertical이 수직선의 개수 verticalLines보다 작을 때까지 반복문을 진행한다.

현재 수직선 번호 뒤에 있는 수직선 번호를 backPoint라고 하고, vertical + 1을 해준다.

만일,

• backPoint가 수직선의 개수 범위 내에 있고
• backPoint가 현재 탐색중인 높이에서 앞번호, 뒷번호와 연결되지 않았다면

현재 수직선과 backPoint를 탐색중인 높이에서 연결시켜준 후,

go(idx + 1, 현재 수직선 번호, 다음 높이)로 다음 번째로 만들 가로선을 탐색한다.

return됐을 경우, 연결시켜준 현재 수직선과 backPoint의 연결상태를 해제시켜준다.

 

그러고난 후에, 높이에 +1을 해줘서 다음 높이를 살펴본다.

만일 높이가 범위를 벗어났다면, 수직선 번호를 다음 번호로 바꾸고,

높이를 1로 바꾼다.

 

백트래킹에서 중복을 제거하는 것이 중요하단 것을 다시 한 번 알게된 문제였다.

뭔가 예전에 중복때문에 틀렸던 것 같은데도 또 까먹었다...

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.