[백준] 백트래킹 - 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를 의미한다. '.'는 매직 스타의 형태를 만들기 위해서 사용하는 문자이다. 모든 입력은 예제 입력과 같은 형태로 주어진다.

 

출력

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

 

예제 입력1

예제 출력1

 

생각

				(0, 4)
	(1, 1)		(1, 3)		(1, 5)		(1 ,7)
		(2, 2)		(2, 4)		(2,6)
	(3, 1)		(3, 3)		(3,5)		(3, 7)
				(4, 4)

별모양을 어떻게 만들어야하나 고민했는데, 인덱스 규칙을 찾으려고 하다가 꼬여버려서

그냥 다른 블로그를 보고 참고했다. 

[참고]https://yabmoons.tistory.com/148

 

' 매직 스타를 만들 수 있는 방법 중에 사전 순으로 가장 앞서는 방법을 출력한다. ' 

출력 조건때문에 고민을 했는데 어차피 DFS호출 순서로 인해 맨 첫번째 출력하는 별 모양이 사전 순으로 가장 앞서게 된다. 

exit(0) 대신 return을 쓰게되면 출력값이 2개 나온다. 

F로 시작하는 것과, G로 시작하는 것

따라서 exit(0)을 써서 강제 종료 시켜줘야한다. 

 

 

작성한 코드

#include <iostream>
#include <stdio.h>
#include <vector>
 
using namespace std;
 
char star[5][9];
bool visited[13];
int cnt = 0;
 
vector< pair<int, int> > v;
 
bool check(){
    if ((star[0][4] - 'A' + 1) + (star[1][3] - 'A' + 1) + (star[2][2] - 'A' + 1) + (star[3][1] - 'A' + 1) != 26) return false;
    if ((star[0][4] - 'A' + 1) + (star[1][5] - 'A' + 1) + (star[2][6] - 'A' + 1) + (star[3][7] - 'A' + 1) != 26) return false;
    if ((star[1][1] - 'A' + 1) + (star[1][3] - 'A' + 1) + (star[1][5] - 'A' + 1) + (star[1][7] - 'A' + 1) != 26) return false;
    if ((star[3][1] - 'A' + 1) + (star[3][3] - 'A' + 1) + (star[3][5] - 'A' + 1) + (star[3][7] - 'A' + 1) != 26) return false;
    if ((star[4][4] - 'A' + 1) + (star[3][3] - 'A' + 1) + (star[2][2] - 'A' + 1) + (star[1][1] - 'A' + 1) != 26) return false;
    if ((star[4][4] - 'A' + 1) + (star[3][5] - 'A' + 1) + (star[2][6] - 'A' + 1) + (star[1][7] - 'A' + 1) != 26) return false;
 
    return true;
}
void DFS(int idx, int n){
    if(n == cnt){
        if(check() == true){ // x의 개수와 방문한 수가 같으면 종료
            for(int i=0; i<5; i++){
                for(int j=0; j<9; j++){
                    cout << star[i][j];
                }
                cout << "\n";
            }
            exit(0);
        }
    }
    for(int i=0; i<12; i++){
        if(visited[i] == true) continue;
        visited[i] = true;
        star[v[idx].first][v[idx].second] = i + 'A';
        DFS(idx+1, n+1);
        star[v[idx].first][v[idx].second] = 'x';
        visited[i] = false;
    }
}
 
int main(int argc, const char * argv[]) {
    // insert code here...
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    for(int i=0; i<5; i++){
        for(int j=0; j<9; j++){
            cin >> star[i][j];
            
            if('A' <= star[i][j] && star[i][j] <= 'L'){ // 알파벳이면 true
                visited[star[i][j] - 'A'] = true;
            }else if(star[i][j] == 'x'){
                v.push_back(make_pair(i, j));
                cnt ++; // x의 개수를 세서 알파벳 채울 갯수 체크
            }
        }
    }
    
    DFS(0,0);
    
    return 0;
}