문제 설명

문제 요약

skyscaper 퍼즐은 퍼즐 바깥 쪽에 해당 열이나 행에서 바라 보았을 때 보이는 건물의 개수를 제시한다.
그러면 우리는 빈 칸에 해당 조건에 맞는 건물의 높이를 기입해야한다.
단, 각 열과 행에는 같은 높이의 건물은 존재할 수 없다.
아래는 퍼즐의 이해를 돕기 위한 그림이다.
왼쪽처럼 각 사람들이 서 있을 때 보이는 건물의 개수가 주어지면 이를 이용하여 실제 건물들을 조건에 맞게 배치한다.

아래는 실제 퍼즐의 예시이다.
왼쪽처럼 퍼즐 바깥쪽에 각 열과 행에 보이는 건물의 개수가 주어지면 이에 맞는 해를 구하면 된다.

문제의 입력은 쉘에서 다음과 같이 주어진다. 위의 예시와는 다르게 모든 행과 열에서 보이는 건물의 개수는 주어진다. (퍼즐 바깥 부분에 빈 칸이 없다.)

다음은 실제 입력과 출력의 예시이다.

그 외 조건

• 사용가능한 함수: malloc, free, write
• 입력이 부정확하거나, 해가 없는 경우 "error" 출력
• 해가 여러개인 경우, 첫 번째로 찾은 해만 출력하고 중지

풀이

분기한정 가지치기

기본적인 아이디어는 백트랙킹을 하되, 유망하지 않은 분기는 가지를 쳐내는 것이다.
틀은 백트랙킹이고, 성능을 좌우하는 것은 어떤 기준으로 분기를 쳐내는가이다.

부록: 문제 원문