백준 2469. 사다리 타기

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

2469번: 사다리 타기

 

처음에 생각없이 백트래킹으로 풀었다가 시간초과나서 다시 풀었다.

 

이 문제는 백트래킹으로는 시간 때문에 풀수 없다.

 

위에서 부터 아래로 감추어진 사다리 가로줄까지 올때까지 타고 내려가고, 

마찬가지로 아래에서 부터 위로 감추어진 사다리 가로줄까지 타고 올라간다. 

 

이렇게 되면 아래로 내려온 알파뱃과, 위로 올라온 알파뱃이 감추어진 사다리 가로줄에서 만난다.

예를들어 주어지는 예제에서는 사다리가 다음과 같다. 

*-***-***
-*-******
?????????
-**-***-*
**-*-*-*-

 

위에서 부터 아래로, 아래에서 부터 위로 타고가면 다음과 같이 감추어진 가로줄을 사이에 두고 만난다. 

(세로줄의 수는 참가 인원 - 1) 

C	A	D	B	E	G	F	H	I	J
?	?	?	?	?	?	?	?	?
C	A	B	D	G	E	F	H	J	I

 

이제 가로줄을 그으면 된다.

위와 아래가 같으면 그냥 내려가면 되기 때문에 줄을 그을 필요가 없다. 

C	A	D	B	E	G	F	H	I	J
*	*	?	?	?	?	*	*	?
C	A	B	D	G	E	F	H	J	I

 

다른 경우에는 사다리를 무조건 놔야한다. 

사다리를 타거나 안타거나 기회가 한번 뿐이기 때문에 복잡하게 생각할것 없이 위 아래가 다르면 안놓아도 되는 경우는 없다. 

그리고 사다리를 놓았으면 다음 세로줄은 사다리를 절대로 놓을수 없다.  

왜냐면 사다리를 두개 연속 놓을수는 없기 때문이다.

 

C	A	D	B	E	G	F	H	I	J
*	*	-	*	-	*	*	*	-
C	A	B	D	G	E	F	H	J	I

 

말했 듯이, 사다리를 탈 수 있는 기회는 단 한번 뿐이기 때문에 사다리를 놓을수 있는 경우는 이것 하나 뿐이다. 

하지만 이렇게 놓았더라도 원하는 순서가 안나올수도 있기 때문에 사다리를 놓은대로 타고 내려가서 정답인지 확인하고 맞다면 출력 아니면 'xxxxxxx' 를 출력하면 된다.