매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 위해서 사용하는 문자이다. 모든 입력은 예제 입력과 같은 형태로 주어진다.
출력
매직 스타를 만들 수 있는 방법 중에 사전 순으로 가장 앞서는 방법을 출력한다. (모든 줄을 순서대로 붙여서 하나의 문자열로 만든 뒤, 사전 순으로 비교한다.) 항상 정답이 존재하는 경우만 입력으로 주어진다.
입력 예시
....x....
.A.I.D.x.
..x...x..
.x.x.x.x.
....x....
출력 예시
....F....
.A.I.D.L.
..H...E..
.C.J.B.K.
....G....
풀이
매직 스타에서, 각 숫자의 유일성이 보장되며 숫자가 위치하는 곳이 항상 동일하므로, 전체 모양에서 빠르게 숫자들을 추출하여 매핑을 시도한 후, 해답을 전체 모양에 다시 맞추어 출력하는 방식이 요구된다.
또한, 1부터 12까지의 숫자는 유일성이 보장되며, 우리가 사전순으로 가장 앞서는 해답을 찾기 위해 순서대로 숫자를 채워나가므로 각 줄이 완성될 때마다 매직 스타의 조건(그 줄의 합이 26이 되는지)을 검사해 볼 수 있겠다. 이렇게 하여 마지막 idx까지 채워넣을 수 있다면, 이 숫자들이 해답이 되므로 즉시 출력하면 된다.
풀이 코드
import sys
sys.setrecursionlimit(100000)
star_list = [0]*12
visited = [False]*13
line_list = [
(0, 2, 5, 7),
(0, 3, 6, 10),
(7, 8, 9, 10),
(1, 2, 3, 4),
(1, 5, 8, 11),
(4, 6, 9, 11)
]
coord_list = [
(4, 0), (1, 1), (3, 1), (5, 1), (7, 1),
(2, 2), (6, 2), (1, 3), (3, 3), (5, 3), (7, 3),
(4, 4)
]
map_list = [input().strip() for _ in range(5)]
result = [['.']*9 for _ in range(5)]
def check(idx) :
for line in line_list :
if line[-1] >= idx :
continue
tmp = 0
for l in line :
tmp += star_list[l]
if tmp != 26 :
return False
return True
def encode() :
for i in range(12) :
x, y = coord_list[i]
if map_list[y][x] != 'x' :
star_list[i] = ord(map_list[y][x]) - ord('A') + 1
visited[star_list[i]] = True
def decode() :
for i in range(12) :
x, y = coord_list[i]
result[y][x] = chr(ord('A') + star_list[i] - 1)
for _result in result :
print(''.join(_result))
def dfs(idx) :
if idx in [5, 8, 11, 12] :
if not check(idx) :
return False
if idx == 12 :
decode()
return True
if star_list[idx] > 0 :
return dfs(idx+1)
for i in range(1, 13) :
if visited[i] :
continue
star_list[idx] = i
visited[i] = True
tmp = dfs(idx+1)
if tmp :
return True
star_list[idx] = 0
visited[i] = False
return False
encode()
dfs(0)
