직소 퍼즐 맞추기
면접 대비시간 제한1초메모리 제한128 MB
각 퍼즐 조각에 위, 왼쪽, 아래, 오른쪽 정수 값이 주어지며, 서로 반대되는 값을 맞춰 N x N 격자의 제자리에 배치한 뒤 완성된 그림을 출력한다.
문제
직소(조각) 퍼즐을 맞추는 프로그램을 작성한다. 입력에는 퍼즐의 크기, 조각의 크기, 그리고 모든 조각이 주어진다. 각 조각은 ASCII 문자로 그려져 있다. 프로그램은 조각들을 올바른 위치에 배치한 완성된 퍼즐을 출력해야 한다.
입력
첫째 줄에 세 정수 , , 가 주어진다. 각각 퍼즐의 한 변에 놓인 조각 수(퍼즐은 항상 조각으로 이루어진 정사각형이다), 조각의 높이, 조각의 너비이다. 모든 조각의 크기는 같다. 범위는 , 이다. 예를 들어 2 2 3은 각 조각이 높이 , 너비 문자인 퍼즐을 뜻한다.
이어서 개의 조각이 임의의 순서로 주어진다. 각 조각은 그 이미지(정확히 줄, 각 줄 문자)와 그다음 줄에 놓인, 범위의 네 정수로 이루어진다. 이 네 값은 순서대로 위, 왼쪽, 아래, 오른쪽 변의 모양이다. 값 은 곧은(바깥쪽) 변을 뜻한다. 두 변은 값의 부호가 반대이고 합이 일 때 정확히 맞물린다(예: 는 와, 는 와 맞물린다). 조각은 회전할 수 없으며, 네 변의 값이 모두 같은 두 조각은 존재하지 않는다(모든 조각은 서로 다르다). 조각과 조각 사이는 빈 줄 하나로 구분된다.
공백 문자(ASCII 32)도 조각을 이루는 유효한 문자이며, 줄 끝이나 한 줄 전체를 포함해 어디에나 나타날 수 있고, 해당 위치에 그대로 입력에 포함된다. 모든 조각은 문자(ASCII 32~127)로 채워진 직사각형 블록이므로, 공백도 다른 문자와 똑같이 취급한다.
출력
완성된 퍼즐을 출력한다. 개의 조각을 배치하는 방법은 유일하다. 모든 바깥쪽 변(값 )은 퍼즐의 테두리에 놓이고, 각 조각의 오른쪽 변과 그 오른쪽 이웃 조각의 왼쪽 변의 합이 이며, 각 조각의 아래쪽 변과 그 아래 조각의 위쪽 변의 합이 이 되도록 맞춘다. 이렇게 완성된 그림, 즉 줄, 각 줄 문자를 출력한다. 입력에는 항상 정확히 하나의 해가 존재한다.