이번 문제는 백트레킹을 통해 모든 경우를 확인하여 해결하였다. 이 문제를 해결하기 위해 다음과 같은 방식으로 접근하였다.

• 매직스타의 위, 왼쪽부터 아래, 오른쪽으로 이동하며 인덱스를 부여했다. (0 ~ 11)
• 일직선으로 위치하는 인덱스들에 대한 조건 판별을 하는 함수를 작성하였다.
  • 일직선으로 위치하는 값들의 합을 ord() 내장함수를 통해 계산하였고, 이 합은 26과 같은 것이 아니라 22+ord('A')*4와 같도록 해야 한다.
• 중복된 알파벳을 사용할 수 없으므로 defaultdict를 이용하여 방문 처리 딕셔너리를 만들었다.
• 백트레킹은 순서대로 확인하기 때문에 조건 판별 함수에서 True를 반환할 경우, 이떄의 결과값이 사전순으로 가장 빠른 것이므로, flag를 True로 갱신하고, flag가 True일 경우에 다른 분기들은 종료되도록 하여 시간을 줄였다.

Code

from collections import defaultdict
s = [list(str(input())) for _ in range(5)]
star = ['' for _ in range(12)]
idx = 0
visited = defaultdict(bool)
for i in range(5):
    for j in range(9):
        if s[i][j].isalpha():
            star[idx] = s[i][j]
            idx += 1
            if s[i][j] != 'x':
                visited[s[i][j]] = True
apb = [chr(i) for i in range(ord('A'), ord('L')+1)]
def chk():
    if not (ord(star[0]) + ord(star[2]) + ord(star[5]) + ord(star[7]) == 22 + ord('A')*4):
        return False
    if not (ord(star[1]) + ord(star[2]) + ord(star[3]) + ord(star[4]) == 22 + ord('A')*4):
        return False
    if not (ord(star[0]) + ord(star[3]) + ord(star[6]) + ord(star[10]) == 22 + ord('A')*4):
        return False
    if not (ord(star[7]) + ord(star[8]) + ord(star[9]) + ord(star[10]) == 22 + ord('A')*4):
        return False
    if not (ord(star[1]) + ord(star[5]) + ord(star[8]) + ord(star[11]) == 22 + ord('A')*4):
        return False
    if not (ord(star[4]) + ord(star[6]) + ord(star[9]) + ord(star[11]) == 22 + ord('A')*4):
        return False
    return True
ans = []
flag = False
def magic_star(cur, mstar,):
    global ans, flag
    if flag:
        return
    if cur == 12:
        if chk():
            flag = True
            ans = mstar[:]
        return
    if mstar[cur] != 'x':
        magic_star(cur+1, mstar)
    else:
        for i in range(len(apb)):
            if not visited[apb[i]]:
                mstar[cur] = apb[i]
                visited[apb[i]] = True
                magic_star(cur+1, mstar)
                visited[apb[i]] = False
                mstar[cur] = 'x'
                if flag:
                    return
magic_star(0, star)
idx = 0
for i in range(5):
    for j in range(9):
        if s[i][j].isalpha():
            s[i][j] = ans[idx]
            idx += 1
for i in range(5):
    print(''.join(s[i]))