[백준 3967] 매직스타 -JAVA //le_effort

매직 스타 성공출처다국어분류한국어

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1208	573	418	49.351%

문제

매직 스타는 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

xxxxxxxxxx
....x....
.A.I.D.x.
..x...x..
.x.x.x.x.
....x....

예제 출력 1

....F....
.A.I.D.L.
..H...E..
.C.J.B.K.
....G....

 

 

풀이

문제를 읽고 맨 처음에 든 생각은 백트래킹을 이용해서 문제를 풀면 되겠다 였다

근데 백트래킹에 대한 시간 복잡도 구하는 것을 잘 몰라서

저렇게 한 칸마다 A~L 씩 넣고 다음단계에서 첫번째 단계에서 넣지 않은 알파벳 11개를 넣어보고.... 이런식으로 하면 연산시간이 무지막지하게 많지 않을까?

라는 막연한 생각이 들었다.

 

그래서 조금 더 고민해보다가 남들 블로그를 봤는데 다 백트래킹으로 하는 것 이였다

결국 백트래킹을 통해서 해결을 하고 난 후에 시간복잡도를 구해봤다.

 

시간복잡도 연습해보기

문제에서 알파벳은 A~L 즉 최대 12개이다

만약에 이 문제에서 전부 다 빈칸인 경우라면 어떻게 할 까?

1번째 칸에 12개 숫자중 1개

2번째칸에 11개의 숫자중 1개 (1번째 칸에서 1개를 사용했으니 그걸 제외한 11개임)

3번째 칸에 10개의 숫자중 1개

. . .

12번째 칸에 1개의 숫자중 1개

 

순열로 표현하면 12P12 이고 이는 즉 12! 임을 알 수 있다

12! 일 경우 연산 횟수는 479,001,600

즉 1초의 연산횟수를 뛰어 넘는다고 볼 수 있다.

 

하지만 이 문제에서 <일부만 채워진 매직 스타가 주어졌을 때> 라는 조건이 있다

최악의 경우를 생각해보면 12개의 칸 중 1 칸만 채워 졌을 수 있다

이 때 시간 복잡도는 11! 이다

11! 일 경우 연산량은 39,916,800 이고 1초 안에 무난히 들어 올 수 있다.

 

즉 그래서 백트래킹을 사용해서 이 문제를 1초 안에 해결 할 수 있는 것이다.

 

그리고 시간복잡도 공부하면서 더 배웠던 부분도 써보려고 한다.

문제 1) 12개의 숫자를 사용 할 수 있고 2칸에 채울 경우 연산량은?

문제 2) 100개의 숫자를 사용 할 수 있고 2칸에 채울 경우 연산량은?

 

문제 1의 경우 12p2 이다

첫번째 칸에 채울수 있는 경우의 수는 12가지이고

두번째 칸에 채울수 있는 경우의수는 11가지이다 (첫번째 칸에서 쓴 것을 제외)

그럼 12x11 이 연산량이다

 

문제 2의 경우는 100p2 이므로 100x99 가 되겠다.

 

 

 

전체코드

아 그리고 문제에서 적혀있는 사전순으로 제일 빠른것을 출력 하라는 것은

따로 값을 구하고 정렬을 하라는게 아닌

그냥 A 순서부터 L까지 백트래킹을 진행하다가

처음으로 조건을 만족 하면 출력하고 프로그램을 종료하면 된다.

 

import java.io.*;
import java.util.*;
public class Main {
    static char map[][] = new char[5][9];
    static boolean visited[] = new boolean[13];
    static ArrayList<Node>list = new ArrayList<>(); // 알파벳으로 채워야 할 곳을 담아두는 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // A-64 = 1
        
        for(int i=0; i<5; i++) {
            String str = br.readLine();
            for(int j=0; j<9; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j]=='x') {
                    list.add(new Node(i,j));
                }
                else if(map[i][j]!='.') {
                    visited[map[i][j]-65] = true;
                }
            }
        }
        dfs(0);
    }
    public static void dfs(int idx) {
        if(idx == list.size()) {
            if(check()) {
                for(int i=0; i<5; i++) {
                    for(int j=0; j<9; j++) {
                        System.out.print(map[i][j]+"");
                    }
                    System.out.println();
                }
                System.exit(0);
            }
            else {
                return ;
            }
        }
        for(int i=0; i<12; i++) {   // A~L 까지 탐색
            
            if(!visited[i]) {   // 해당 알파벳이 쓰이지 않았다면
                Node a = list.get(idx);
                char alpha = (char) (65+i);
                map[a.x][a.y]= alpha;
                visited[i] = true;
                dfs(idx+1);
                visited[i] = false;
                map[a.x][a.y]= '.'; 
            }
        }
    }
    public static boolean check() {
        int sum1 = (map[0][4]-'A'+1) + (map[1][3]-'A'+1)+ (map[2][2]-'A'+1)+(map[3][1]-'A'+1);
        int sum2 = (map[0][4]-'A'+1)+(map[1][5]-'A'+1)+(map[2][6]-'A'+1)+(map[3][7]-'A'+1);
        int sum3 = (map[1][1]-'A'+1)+(map[1][3]-'A'+1)+(map[1][5]-'A'+1)+(map[1][7]-'A'+1);
        int sum4 = (map[3][1]-'A'+1)+(map[3][3]-'A'+1)+(map[3][5]-'A'+1)+(map[3][7]-'A'+1);
        int sum5 = (map[4][4]-'A'+1)+(map[3][3]-'A'+1)+(map[2][2]-'A'+1)+(map[1][1]-'A'+1);
        int sum6 = (map[4][4]-'A'+1)+(map[3][5]-'A'+1)+(map[2][6]-'A'+1)+(map[1][7]-'A'+1);
        
        if(sum1==26 && sum2 ==26 && sum3==26 && sum4==26 && sum5==26 && sum6==26) {
            return true;
        }
        return false;
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<5 && y<9) {
            return true;
        }
        return false;
    }
}
class Node{
    int x, y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}