[자바] 백준 24891 - 단어 마방진 (java)

목차

문제 : boj24891

 

 

필요 알고리즘

• 브루트 포스
  
  • 그냥 모든 경우를 다 확인해보면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  최악의 경우가 20개의 단어 중 5개를 순서대로 뽑는 경우이므로 20P5 = 20*19*18*17*16 번 정도면 모든 경우를 다 확인할 수 있다. 그리고 마방진임을 확인하는데에는 최대 L^2 이면 확인 가능하다. 결론적으로 그냥 브루트포스로 모든 경우를 확인하면 되는 문제이다. O(NPL * L^2) = 최악의 경우 대략 4650만번. 백트래킹으로 좀 더 효율성을 챙길 순 있지만, 입력 데이터에 따라 백트래킹이 의미 없는 경우가 있을꺼라 굳이..? 느낌이긴 하다.

 

   그럼 이제 필요한건 N개 중 L개를 잘 선택하고, 그게 마방진이 맞는지만 확인하는 코드를 구현만 하면 된다. 구현 방법이야 여러가지일테고, 내 경우엔 가장 간단하게 짤 수 있는 재귀로 짰다. 참고로 사전 순으로 가장 빠른 단어 마방진은, 그냥 입력 받은걸 미리 정렬해두고 사전 순으로 빠른 단어부터 선택해 만들어보다가, 마방진 완성되면 끝내면 그게 가장 빠른 단어 마방진이다.

private void find(final int choiceCnt) {
    if (choiceCnt == n) {	// 코드에서 N이 문제의 L이다. L은 헷갈려서 이걸 N으로 바꿈.
        if (isMagicSquare()) isEnd = true;	// 마방진 맞으면 끝냄
        return;
    }

    for (int i = 0; !isEnd && i < words.length; i++) {
        if (v[i]) continue;	// 아직 선택하지 않은 단어라면
        v[i] = true;	// 선택하고
        choice[choiceCnt] = words[i];	// 현재 선택은 i 인덱스의 단어
        find(choiceCnt+1)	// 다음 스탭
        v[i] = false;
    }
}

private boolean isMagicSquare() {	// 마방진 맞는지 확인한다.
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (choice[i].charAt(j) != choice[j].charAt(i)) return false;
        }
    }
    return true;
}

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private boolean isEnd = false;
    String[] words, choice;
    boolean[] v = new boolean[20];
    int n;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        words = new String[w];
        while (w-->0) words[w] = br.readLine();

        Arrays.sort(words);
        choice = new String[n];
        find(0);

        if (!isEnd) {
            System.out.println("NONE");
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(choice[i]).append('\n');
        }
        System.out.print(sb);
    }

    private void find(final int choiceCnt) {
        if (choiceCnt == n) {
            if (isMagicSquare()) isEnd = true;
            return;
        }

        for (int i = 0; !isEnd && i < words.length; i++) {
            if (v[i]) continue;
            v[i] = true;
            choice[choiceCnt] = words[i];
            find(choiceCnt+1);
            v[i] = false;
        }
    }

    private boolean isMagicSquare() {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (choice[i].charAt(j) != choice[j].charAt(i)) return false;
            }
        }
        return true;
    }
}