[CDJ] 2017 Round 1A - A. Alphabet Cake

문제 링크

CodeJam 2017 Round 1A A번 문제 Alphabet Cake

[CodoeJam]

출처 : https://code.google.com/codejam/contest/5304486/dashboard

[백준 알고리즘]

참고(Small) : https://www.acmicpc.net/problem/14797

참고(Large) : https://www.acmicpc.net/problem/14798

문제 요약

- (R X C)의 행열 케이크가 주어진다.

- 행열 케이크에는 아이의 이니셜이 알파벳 대문자(A~Z)로 하나씩 있다. 

- 이니셜이 없는 빈 자리에는 ?를 표시한다.

- 이니셜이 있는 자리는 ?를 포함하여 하나의 직사각형 케이크를 만들 수 있다. 이때 ?를 해당 이니셜로 대체한다.

- 빈 자리가 없도록 이니셜을 포함하여 직사각형의 케이크를 나누고자 한다.

- 이니셜은 중복되어 나타나지 않는다.

- 꼭 공평하게 케이크를 나눌 필요는 없다.

- 이니셜이 있는 1X1 크기도 직사각형으로 본다.

입출력

입력 

Small

• 1 ≤ T ≤ 100. (테스트 케이스 횟수)
• There is at least one letter in the input grid.
• No letter appears in more than one cell in the input grid.
• It is guaranteed that at least one answer exists for each test case.
• 1 ≤ R ≤ 12. (행)
• 1 ≤ C ≤ 12. (열)
• R × C ≤ 12. 

Large

• 1 ≤ T ≤ 100.
• There is at least one letter in the input grid.
• No letter appears in more than one cell in the input grid.
• It is guaranteed that at least one answer exists for each test case.
• 1 ≤ R ≤ 25.
• 1 ≤ C ≤ 25.

출력

각 테스트 케이스는 "Case #x:" 로 표시하며 그 다음 줄에 결과를 출력한다.

결과는 직사각형 이니셜이 새겨진 RXC 행렬의 케이크를 출력한다.

예제 입력

3
3 3
G??
?C?
??J
3 4
CODE
????
?JAM
2 2
CA
KE

예제 출력

Case #1:
GGJ
CCJ
CCJ
Case #2:
CODE
COAE
JJAM
Case #3:
CA
KE

문제 해설

이 문제는 가장 큰 사이즈여도 R,C 가 25 이기 때문에 시간 복잡도를 크게 고려할 필요가 없는

완전 탐색으로 풀 수 있을 것이라 판단하였다.

처음엔 "직사각형을 만들어야한다"는 것만 생각하고 복잡한 알고리즘을 구현하였다.

Start(x1, y1)점과 End(x2, y2)지점을 지정하여 이니셜이 있고 최대 사이즈의 직사각형을 찾아 해당 이니셜로 채워나가도록 하였다.

이 방법의 문제는 각 지점에 대한 메모리를 많이 필요하게 되었고, 

최대의 사이즈의 직사각형을 필요하지 않았으며(?만 없어도 됨), 

시간 복잡도도 O((RXC)^2)으로... 좋은 알고리즘은 아니라 생각된다.

하지만 RXC의 크기가 매우 작기 때문에 해당 코드도 통과될 수 있었다.

-------

그럼 이제 다시 보다 최적화된 코드를 생각해 보자...

이 문제를 단순하게 변경하여 이니셜을 페인트 물감색이라 가정하면 벽에 부분 부분 물감을 뿌리고 롤러를 쭉 가로로 먼저 문지르고 다음 세로로 문지른다면

자연스럽게 빈공간을 채우면서 직사각형의 물감색을 칠할 수 있을 것이다.

예를 들어 다음과 같은 입력이 주어진다면

C	?	?	?
?	O	D	?
J	?	M	?
?	?	?	?

각 이니셜 별로 서로 겹치지 않게 가로로 쭉 채워주고

C	C	C	C
O	O	D	D
J	J	M	M
?	?	?

각 이니셜 별로 서로 겹치지 않게 다시 세로로 쭉 채워주면 직사각형이 완성된다.

C	C	C	C
O	O	D	D
J	J	M	M
J	J	M	M

결국 단순한 규칙만 파악하면 쉽게 풀리는 문제로 코드역시 단순하다.

해당 문제의 시간 복잡도는 RXC를 돌면서 이니셜을 찾아 가로로 채워주고, 같은 방법으로 세로로 채움으로 O(2(RXCX(C or R))) 복잡도를 가진다.

소스 코드

복잡한 코드는 후에 다시 볼 때 반성의 의미로 함께 올려 둔다...

첫번째 코드가 처음 복잡하게 짠 알고리즘이며 두번째 코드가 다시 최적화하여 짠 알고리즘이다.