백준 - 2784번(가로 세로 퍼즐)

문제 출처: https://www.acmicpc.net/problem/2784

문제

• 아래와 같은 가로 세로 퍼즐을 풀어보자.

• 가로줄

  1. device used to cool a PC
  2. solid water
  3. to obtain

• 세로줄

  1. small, soft, sweet fruit
  2. strong playing card
  3. fisherman's tool

• 6개의 단어가 주어졌을 때, 이를 가지고 가로 세로 퍼즐을 만드는 프로그램을 작성하시오. 단어 3개는 가로줄, 3개는 세로줄로 배치해야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    private static boolean[] visited; // 방문 기록
    private static List<String> word;     // 문자열 저장

    private static List<List<String>> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        word = new ArrayList<>(6);
        visited = new boolean[6];
        for (int i = 0; i < 6; i++) {
            word.add(reader.readLine());
        }

        permutation(new int[3], 0, 3);

        if (list.isEmpty()) sb.append(0);
        else {
            for (int i = 0; i < 3; i++) {
                sb.append(list.get(0).get(i)).append("\n");
            }
        }

        System.out.println(sb);
    }

    private static void permutation(int[] ans, int cnt, int R) {
        if (cnt == R) {
            // 3개 다 뽑은 경우
            List<String> temp = new ArrayList<>(3);
            List<String> copy = new ArrayList<>(6);
            copy.addAll(word);

            // 뽑은 3개 단어 넣기
            for (int i = 0; i < 3; i++) {
                temp.add(word.get(ans[i]));
                copy.remove(word.get(ans[i]));
            }

            // 퍼즐이 성립하는지 비교
            for (int i = 0; i < 3; i++) {
                String tempStr = "" +
                        temp.get(0).charAt(i) +
                        temp.get(1).charAt(i) +
                        temp.get(2).charAt(i);

                if (copy.contains(tempStr)) copy.remove(tempStr);
                else return;
            }
            list.add(temp);

            return;
        }

        for (int i = 0; i < 6; i++) {
            if (!visited[i]) {
                visited[i] = true;
                ans[cnt] = i;
                permutation(ans, cnt + 1, R);
                visited[i] = false;
            }
        }
    }

}

• 효율적인 방법이 없을까 이리저리 고민하다 그냥 순열로 풀었다.
• 6개의 단어 중 3개만 뽑으면 되기 때문에 그리 오래 걸리지 않았다.