[백준 3967 🥇] 매직 스타

문제

매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다.

매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26이 되기 때문이다. 위의 그림의 여섯 줄에 쓰여 있는 숫자는 다음과 같다.

• 1 + 4 + 10 + 11
• 11 + 5 + 3 + 7
• 7 + 6 + 12 + 1
• 2 + 10 + 5 + 9
• 9 + 3 + 6 + 8
• 8 + 12 + 4 + 2

매직 스타를 채우는 방법은 여러 가지가 있다. 일부만 채워진 매직 스타가 주어졌을 때, 수를 전부 다 채워서 매직 스타를 만드는 프로그램을 작성하시오.

입력

매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 위해서 사용하는 문자이다. 모든 입력은 예제 입력과 같은 형태로 주어진다.

출력

매직 스타를 만들 수 있는 방법 중에 사전 순으로 가장 앞서는 방법을 출력한다. (모든 줄을 순서대로 붙여서 하나의 문자열로 만든 뒤, 사전 순으로 비교한다.) 항상 정답이 존재하는 경우만 입력으로 주어진다.

문제 풀이

• DFS를 이용한 완전 탐색을 했다!
• 우선, A~L까지 12개의 대문자 알파벳을 이미 가지고 있는지 저장하기 위한 배열 visited를 선언한다.
• 그리고 'x'가 위치한 좌표를 저장하기 위한 배열 X를 선언하고, 'x'의 개수를 X_cnt 변수에 저장해준다.
• 입력받은 hexagram의 정보를 돌면서 위에서 설명한 각각의 배열에 값을 저장한다.
• 그리고 DFS를 이용해서 위에서 저장한 X 배열에 저장된 'x'의 위치를 차례로 돌면서, 해당 위치에 A~L 중 아직 방문하지 않은 알파벳을 넣어준다.
• 그 상태에서 DFS로 재귀탐색을 한다. 탐색 과정에서 'x'의 위치에 알파벳을 넣어준 개수 cnt가 X_cnt와 동일해졌다면, 6개의 모든 줄이 각 값을 더했을 때 26이 되는지 calculate_hexagram() 함수를 이용해서 확인한다. 만약 이 조건을 만족한다면, 우리는 첫 번째 'x'의 위치부터 차례대로, 'A'부터 'L'까지 차례대로 탐색하고 있으므로 가장 먼저 이 조건을 만족하는 hexagram이 사전순으로 가장 앞서는 정답이 된다. 
• 그러므로 조건을 만족하자마자 해당 hexagram을 출력하고 프로그램을 종료한다. 

import sys

hexagram=[]
for _ in range(5):
    line=list(sys.stdin.readline().strip())
    hexagram.append(line)

# A~L
visited=[0]*(13)
# x의 좌표
X=[]
# x의 개수
X_cnt=0
for i in range(5):
    for j in range(9):
        if hexagram[i][j]=='x':
            X.append((i,j))
            X_cnt+=1
        elif hexagram[i][j]=='.':
            pass
        else:
            visited[ord(hexagram[i][j])-65+1]=1


def calculate_hexagram():
    if (ord(hexagram[0][4])-65+1)+(ord(hexagram[1][3])-65+1)+(ord(hexagram[2][2])-65+1)+(ord(hexagram[3][1])-65+1)!=26:
        return False
    if (ord(hexagram[0][4])-65+1)+(ord(hexagram[1][5])-65+1)+(ord(hexagram[2][6])-65+1)+(ord(hexagram[3][7])-65+1)!=26:
        return False
    if (ord(hexagram[1][1])-65+1)+(ord(hexagram[1][3])-65+1)+(ord(hexagram[1][5])-65+1)+(ord(hexagram[1][7])-65+1)!=26:
        return False
    if (ord(hexagram[3][1])-65+1)+(ord(hexagram[3][3])-65+1)+(ord(hexagram[3][5])-65+1)+(ord(hexagram[3][7])-65+1)!=26:
        return False
    if (ord(hexagram[1][1])-65+1)+(ord(hexagram[2][2])-65+1)+(ord(hexagram[3][3])-65+1)+(ord(hexagram[4][4])-65+1)!=26:
        return False
    if (ord(hexagram[1][7])-65+1)+(ord(hexagram[2][6])-65+1)+(ord(hexagram[3][5])-65+1)+(ord(hexagram[4][4])-65+1)!=26:
        return False
    return True

# idx : 배열 X에 저장된 x가 위치한 idx번째 좌표
# cnt : 다른 알파벳으로 채워진 x의 개수
def DFS(idx, cnt):
    if cnt==X_cnt:
        # 모든 줄의 합이 26이면 hexagram 출력하고 프로그램 종료
        if calculate_hexagram():
            for hex in hexagram:
                print(*hex, sep='')
            sys.exit(0)
        # 아니라면 DFS return
        return

    for i in range(1,13):
        # 이미 채워진 알파벳이라면 다음 알파벳 체크
        if visited[i]==1:
            continue
        # 현재 알파벳으로 현재 idx에 해당하는 x의 위치를 채운다면
        visited[i]=1
        hexagram[X[idx][0]][X[idx][1]]=chr(65+i-1)
        DFS(idx+1, cnt+1)
        hexagram[X[idx][0]][X[idx][1]]='x'
        visited[i]=0

DFS(0,0)