[프로그래머스] 단체사진 찍기(2017 카카오 코드 본선) - 자바, DFS(깊이 우선 탐색)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/1835

문제 풀이

• DFS(깊이 우선 탐색)을 사용하여 순열을 만들고 주어진 조건을 만족하는지 검사한다.
• 어떤 이유인지는 잘 모르겠지만, answer를 solution 메서드에서 초기화해주지 않으면 프로그래머스 테스트에서 통과가 되지 않는다.

class Solution {
    static String[] conditions;
    static int[] check;
    static char[] arr;
    static char[] friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    static int answer, nLen;

    public int solution(int n, String[] data) {
        answer = 0; //solution에서 초기화를 해줘야 테스트가 통과된다.
        nLen = n;
        conditions = data;
        check = new int[friends.length];
        arr = new char[friends.length];

        dfs(0);

        return answer;
    }

    public void dfs(int level) {
        if(level == friends.length) {
            boolean flag = true;

            for(int i = 0; i < nLen; i++) {
                int f1 = getPosition(arr, conditions[i].charAt(0));
                int f2 = getPosition(arr, conditions[i].charAt(2));
                char op = conditions[i].charAt(3);
                int value = Character.getNumericValue(conditions[i].charAt(4)) + 1;

                if((op == '=' && Math.abs(f1 - f2) != value) || 
                   (op == '<' && Math.abs(f1 - f2) >= value) || 
                   (op == '>' && Math.abs(f1 - f2) <= value)) {
                    flag = false;
                    break;
                }
            }

            if(flag) answer++;
        } else {
            for(int i = 0 ; i < friends.length; i++) {
                if(check[i] == 0) {
                    check[i] = 1;
                    arr[level] = friends[i];
                    dfs(level + 1);
                    check[i] = 0;
                }
            }
        }
    }

    //배열에서 문자 c의 위치가 어디인지 리턴해주는 메서드
    public int getPosition(char[] arr, char c) {
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == c) {
                return i;
            }
        }

        return -1;
    }
}