단체사진 찍기

import java.util.*;
class Solution {
        static int answer;
        static String[] datas;
    
        public void DFS(ArrayList<String> list, ArrayList<String> res, int i, int n) {
        // 마지막 배열을 입력했을 때
        if (i == 0) {
            for (int j = 0; j < datas.length; j++) {
                // 문자 파싱
                char c1 = datas[j].charAt(0);
                char c2 = datas[j].charAt(2);
                char op = datas[j].charAt(3);
                int num = datas[j].charAt(4) - '0';
                int dis = Math.abs(res.indexOf(String.valueOf(c1)) - res.indexOf(String.valueOf(c2))) - 1;
                if (op == '=') {
                    if (dis != num) {
                        return;
                    }
                } else if (op == '<') {
                    if (dis >= num) {
                        return;
                    }
                } else {
                    if (dis <= num) {
                        return;
                    }
                }
            }
            answer++;
            return;
        }
        // 선택한 문자를 list에서 제거하고 res에 추가하여 탐색, 다음에 탐색하기 위해 다시 복구
        // 제거하기 때문에 n - 1 하여 수행
        for (int k = 0; k < n; k++) {
            res.add(list.remove(k));
            DFS(list, res, i - 1, n - 1);
            list.add(k, res.remove(res.size() - 1));
        }
    }
    
    public int solution(int n, String[] data) {
        ArrayList<String> list = new ArrayList<String>(Arrays.asList("A", "C", "F", "J", "M", "N", "R", "T"));
        ArrayList<String> res = new ArrayList<String>();
        datas = data;
        answer = 0;
 
        DFS(list, res, 8, 8);
        
        return answer;
    }
}

처음에 봤을 때 어떻게 풀어야 하는지 감도 잡을 수 없어서 다른 풀이를 참고하였다.

이 문제는 모든 배치하는 경우에서 조건에 맞지 않는 경우를 제외한 경우의 수를 구하는 문제이다.

총 경우의 수는 8! = 40320이며 이 경우를 모두 탐색하였다.

 

모든 탐색하는 경우는 DFS를 통해 의외로 쉽게 구할 수 있었다.

하지만 인자로 넘기는 변수들이 다시 원래 상태로 돌아오는 과정이 필요했다.

이를 위해 remove, add를 통해 원래대로 복구시켰다.

 

참고 사이트 : https://gre-eny.tistory.com/104