[백준] 3967번 매직스타

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. 현재 매직 스타의 모양을 입력받는다.

  ('A' ~ 'L'까지 중 어떤 알파벳이 이미 사용됬다면, visited[]에 표시해놓는다.)

2. 매직스타는 총 12개의 문자가 들어가야한다.

   따라서 int star[12]를 선언해서 매직스타의 현재 상태를 저장해 놓는다.

   상태 'A' ~ 'L' = 0 ~ 11로 대응

   

 매직스타

  

  ex) star[1] = 0 // 1위치에 'A'가 저장되어있다.

 star[4] = 10 // 4위치에 'K'가 저장되어있다.

 star[3] = 55 // 3위치는 채워야 하는 위치 즉 'x'이다.

    55가 나오는 이유 => ASCII로 'x' - 'A' == 55

3. 매직스타 중 채워야 하는 위치('x' 즉 star[i]가 55)를 따로 저장해 둔다.

4. 채워야 하는 위치들에 'A' ~ 'L'까지 중 사용하지 않은 알파벳들을 다 넣어보며 정답을 찾는다.

   (재귀방법을 사용)

5. 정답이 나온 경우 출력해준다.

코드)

#include <stdio.h>
#include <vector>
using namespace std;
 
char map[5][10];
int star[12];
bool visited[26];
int check_idx[6][4] = { {0,2,5,7}, {1,2,3,4},{7,8,9,10},{1,5,8,11},{4,6,9,11},{0,3,6,10 } };
bool answer;
vector <int> change;
 
bool Success() {
    for (int i = 0; i < 6; i++) {
        int temp = 0;
        for (int j = 0; j < 4; j++) {
            temp += star[check_idx[i][j]];
        }
        if (temp != 22) return false; //합이 원래는 26이나 'A'~ 'L'를 0 ~ 11로 계산했으니 총 합은 22로 본다.
    }
    
    return true;
}
 
void dfs(int idx) {
    if (answer) return;
    if (idx == change.size()) {
        if (Success()) answer = true;
        return;
    }
    
    for (int i = 0; i < 12; i++) {
        if (visited[i])continue;
        visited[i] = true;
        star[change[idx]] = i;
        dfs(idx + 1);
        visited[i] = false;
        if (answer) return;
    }
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            map[i][j] = getchar();
            if (map[i][j] >= 'A' && map[i][j] <= 'Z') {
                visited[map[i][j] - 'A'] = true;
            }
        }
        getchar();
    }
    
    star[0] = map[0][4]  - 'A'; //매직스타의 현재 상황을 저장
    star[5] = map[2][2] -'A';
    star[6] = map[2][6] - 'A';
    star[11] = map[4][4] - 'A';
    int tmp = 1;
    for (int i = 1; i < 8; i+=2) {
        star[tmp] = map[1][i] - 'A';
        star[tmp + 6] = map[3][i] - 'A';
        tmp++;
    }
    
    for (int i = 0; i < 12; i++) {                //'x' - 'A' = 55
        if (star[i] == 55) change.push_back(i);//채워야하는 위치 저장
    }
 
    dfs(0);
 
    map[0][4] = star[0] + 'A'; //정답으로 나온 알파벳 순서를 다시 매직스타에 저장
    map[2][2] = star[5] + 'A';
    map[2][6] = star[6] + 'A';
    map[4][4] = star[11] + 'A';
    tmp = 1;
    for (int i = 1; i < 8; i += 2) {
        map[1][i] = star[tmp] + 'A';
        map[3][i] =star[tmp + 6] + 'A';
        tmp++;
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%c", map[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}