[BOJ] 24891 단어마방진

플랫폼 == 서비스의 근간이 되는 공통 시스템

접근

먼저 배열로 단어들을 받아서 정렬을 했다. 사전 순으로 출력을 해야하기 때문이다.
그리고 순열을 만들어서 마방진인지 체크하고 맞을 경우 출력 후 종료해서 시간을 단축했다.

마방진인지 체크하는 방법은 열과 행을 바꿔서 같은 지 확인하면 된다.

순열을 만들 때는 순서가 상관있기 때문에 결과 배열을 체크해야 하고, 조합을 만들 때는 만들지 않아도 된다.

dfs를 돌 때는 메소드의 재귀를 다 돌고 다음 메소드를 실행한다고 보면 될 듯 (깊이 우선 탐색)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution24891 {
    static int l, n;
    static String[] word, pickedWord;
    static boolean[] visited;
    static int[] picked;
    static ArrayList<String[]> mabang = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        word = new String[n];
        mabang = new ArrayList<>();
        visited = new boolean[n];
        picked = new int[n];
        pickedWord = new String[l];

        for(int i = 0; i < n; i++) {
            word[i] = br.readLine();
        }

        Arrays.sort(word);

        dfs(0);

        System.out.println("NONE");
    }

    static void dfs(int depth) {
        if(depth == l) {
            for(int i = 0; i < l; i++) {
                pickedWord[i] = word[picked[i]];
            }
            if(check()){
                for(int i = 0; i < l; i++) {
                    for(int j = 0; j < l; j++) {
                        System.out.print(pickedWord[i].charAt(j));
                    }
                    System.out.println("");
                }
                System.exit(0);
            };
            return;
        }

        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                picked[depth] = i;
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }

    static boolean check() {
        for(int i = 0; i < l; i++) {
            for(int j = 0; j < l; j++) {
                if(pickedWord[i].charAt(j) != pickedWord[j].charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}