백준 3967. 매직 스타 :: 돼지개발자

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

"DFS 백트래킹"

시간초과로 삽집을 좀 했던 문제.. 알파벳 원소들의 위치를 p 에 저장해 두고, 조합을 만들고 나중에 이 좌표 정보를 가지고 valid 체크를 하였다. (이 p 배열을 그냥 풀어서 쓰면 시간이 많이 줄여진다.....)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
 
    static char[][] map = new char[5][9];
    static boolean[] visited = new boolean[13];
    
    static ArrayList<Node> list = new ArrayList<>();
    static int[][][] p = {
            {{0,4},{1,3},{2,2},{3,1}},
            {{3,1},{3,3},{3,5},{3,7}},
            {{0,4},{1,5},{2,6},{3,7}},
            {{1,1},{1,3},{1,5},{1,7}},
            {{1,1},{2,2},{3,3},{4,4}},
            {{4,4},{3,5},{2,6},{1,7}}
    };
    static int size;
    static boolean ok;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < 9; j++) {
                map[i][j] = temp[j];
                if(temp[j] =='x') {
                    list.add(new Node(i, j));
                }
                else if(temp[j] != '.'){
                    visited[temp[j]-'A'+1] = true;
                }
            }
        }
        
        size = list.size();
        
        solve(0,0);
    }
    
    static void solve( int cnt, int idx) {
        if(ok) return ;
        
        if(cnt == size && check()) {
            ok = true;
            for (int i = 0; i < 5; i++) {
                System.out.println(map[i]);
            }
            return ;
        }
        
        for (int j = 1; j <= 12; j++) {
            if(visited[j]) continue;
                
            Node cur = list.get(idx);
            visited[j] = true;
            map[cur.x][cur.y] = (char)(j+64);
            solve(cnt+1, idx+1);
            visited[j] = false;
            map[cur.x][cur.y] = 'x';
        }
    }
            
    static boolean check() { 
        for (int a = 0; a < 6; a++) {
            int sum = 0;
            for (int i = 0; i < 4; i++) {
                sum += (map[p[a][i][0]][p[a][i][1]] -'A'+1);
            }
            if(sum != 26) return false;
        }
        return true;
    }
}
 
class Node {
    int x;
    int y;
    
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}