백준 3967 (매직 스타) - java

https://www.acmicpc.net/problem/3967

3967번: 매직 스타

백트랙킹을 사용하는 문제이다. 모든 경우의 수를 고려할 경우 시간 초과가 발생하기 때문에 1번부터 12번까지의 빈칸을 기준으로 5 ,8 ,11 ,12 번 째 빈칸이 채워졌을 때마다 검사를 해서 아닌 경우를 걸러줘야 한다. 

 

똥손이라 미안합니다....

입력을 받을 때 2차원 배열을 사용해도 되지만 1차원 배열로도 풀 수 있다. 다만 입력 과정에서 코드의 길이가 길어진다. 취향대로 하면 된다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] board = new int[13];
    static int[] result = new int[13];
    static boolean[] init = new boolean[13]; // 초기에 채워진 경우를 생각하기 위해서
    static boolean[] number = new boolean[13]; // 값이 채워지지 않은 숫자를 알기 위해서
    static boolean[] visit = new boolean[13];

    static boolean get = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=0;i<5;i++)
        {
            String[] line = br.readLine().split("");
            if(i==0)
            {
                char cur = line[4].charAt(0);
                if(cur!='x')
                {
                    board[1] = cur - 'A' + 1;
                }
            }
            if(i==1)
            {
                char cur = line[1].charAt(0);
                if(cur!='x')
                {
                    board[2] = cur - 'A' + 1;
                }
                cur = line[3].charAt(0);
                if(cur!='x')
                {
                    board[3] = cur - 'A' + 1;
                }
                cur = line[5].charAt(0);
                if(cur!='x')
                {
                    board[4] = cur - 'A' + 1;
                }
                cur = line[7].charAt(0);
                if(cur!='x')
                {
                    board[5] = cur - 'A' + 1;
                }
            }

            if(i==2)
            {
                char cur = line[2].charAt(0);
                if(cur!='x')
                {
                    board[6] = cur - 'A' + 1;
                }
                cur = line[6].charAt(0);
                if(cur!='x')
                {
                    board[7] = cur - 'A' + 1;
                }
            }

            if(i==3)
            {
                char cur = line[1].charAt(0);
                if(cur!='x')
                {
                    board[8] = cur - 'A' + 1;
                }
                cur = line[3].charAt(0);
                if(cur!='x')
                {
                    board[9] = cur - 'A' + 1;
                }
                cur = line[5].charAt(0);
                if(cur!='x')
                {
                    board[10] = cur - 'A' + 1;
                }
                cur = line[7].charAt(0);
                if(cur!='x')
                {
                    board[11] = cur - 'A' + 1;
                }
            }

            if(i==4)
            {
                char cur = line[4].charAt(0);
                if(cur!='x')
                {
                    board[12] = cur - 'A' + 1;
                }
            }
        }
        for(int i=1;i<=12;i++)
        {
            if(board[i]>0) {
                init[i] = true;
                number[board[i]] = true;
            }
        }

        makeStar(1);
        print();

        br.close();
    }
    // 결과 출력 함수
    static void print()
    {
        char a = (char)(result[1] + 'A' -1);
        char b = (char)(result[2] + 'A' -1);
        char c = (char)(result[3] + 'A' -1);
        char d = (char)(result[4] + 'A' -1);
        char e = (char)(result[5] + 'A' -1);
        char f = (char)(result[6] + 'A' -1);
        char g = (char)(result[7] + 'A' -1);
        char h = (char)(result[8] + 'A' -1);
        char i = (char)(result[9] + 'A' -1);
        char j = (char)(result[10] + 'A' -1);
        char k = (char)(result[11] + 'A' -1);
        char l = (char)(result[12] + 'A' -1);

        System.out.println("...."+a+"....");
        System.out.println("."+b+"."+c+"."+d+"."+e+".");
        System.out.println(".."+f+"..."+g+"..");
        System.out.println("."+h+"."+i+"."+j+"."+k+".");
        System.out.println("...."+l+"....");
    }
    
    // 백트랙킹으로 별에 빈칸을 채워나간다.
    static void makeStar(int start)
    {
        // 사전 순이기 때문에 순서대로 값을 기입시 첫번째로 완성한 것이 정답이다.
        if(get)
            return;
        
        // 5번 째 빈칸이 채워지고 나서
        if(start==6)
        {
            int num = board[2] + board[3]+ board[4] + board[5];
            if(num!=26)
                return;
        }
        // 8번 째 빈칸이 채워지고 나서
        if(start==9)
        {
            int num = board[1] + board[3] + board[6] + board[8];
            if(num!=26)
                return;
        }
        // 11번 째 빈칸이 채워지고 나서
        if(start==12)
        {
            int num1 = board[1] + board[4]+board[7] + board[11];
            int num2 = board[8] + board[9] + board[10] + board[11];

            if(num1!=26||num2!=26)
            {
                return;
            }
        }
        // 12번 째 빈칸이 채워지고 나서
        if(start > 12)
        {
            int num1 = board[2] + board[6] + board[9] + board[12];
            int num2 = board[5] + board[7] + board[10] + board[12];

            if(num1!=26||num2!=26)
                return;

            if(get==false)
            {
                get = true;
            }
            copy(); // 값을 복사
            return;
        }
        
        // 초기 입력에서 채워진 칸이 아니라면
        if(!init[start]) {
            for (int i = 1; i <= 12; i++) {
                // 해당 숫자가 사용되지 않았고 방문 배열을 통해 백트랙킹
                if (!number[i]&&!visit[i]) {
                    visit[i] = true;
                    board[start] = i;
                    makeStar(start+1);
                    visit[i] = false;
                }
            }
        }
        // 초기 입력에서 채워진 칸이라면 다음 칸으로 이동
        else{
            makeStar(start+1);
        }
    }

    static void copy()
    {
        for(int i=1;i<=12;i++)
        {
            result[i] = board[i];
        }
    }
}