(java) DFS로 순열 구하기

DFS(Depth First Search)를 사용해서 순열 만들기

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

코딩테스트 연습 - 수식 최대화

문제를 해결하던 중 [+. -. *] 을 포함한 모든 경우의 수가 필요했다.
그래서 DFS를 이용한 순열을 구현해보았다.

아래 두 필드는 클래스(전역) 필드이다.

ArrayList<ArrayList<String>> permutedOps = new ArrayList<>(); // 기호들을 담고 있는 리스트를 만들어야 하기 때문에 이중 리스트로 선언
String[] operations = {"+", "-", "*"};

순열을 구하는 permutate() 메소드

private void permutate(boolean[] visited, int depth, String[] output) {
        if (depth == operations.size()) {
            ArrayList<String> newPermutation = new ArrayList<>(Arrays.asList(output));
            permutedOps.add(newPermutation);
            return;
        }

        for (int i = 0; i < operations.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = operations.get(i);
                permutate(visited, depth + 1, output);
                visited[i] = false; // 한 구역의 탐색이 끝났을 때, 방문여부를 false로 되돌려줘야 한다.
            }
        }
}

• 최초로 이 메소드가 호출되었을 때 depth는 0이다.
  • 그러므로 처음엔 if 문에 진입하지 않는다.
• (for문) operations(연산자)를 모두 탐색한다.
  • 처음엔 0번째 인덱스에 저장된 기호를 시작점으로 한다.
  • 0번째 인덱스는 사용했음을 표시하기 위해 visited = true; 로 설정한다.
  • 0번째 인덱스를 시작점으로 했을 때, 재귀적으로 permutate()를 호출함으로써 그 뒤에 올 수 있는 기호들의 모든 경우의 수를 구한다.
  • 즉, 다음의 경우의 수를 구하는 것이다.
    • operations의 0번째 인덱스 사용 - 1번째 인덱스 - 2번째 인덱스
    • 0번째 인덱스 - 2번째 인덱스 - 1번째 인덱스
  • 그다음은 1번째 인덱스에 저장된 기호를 시작점으로 한다... (이하 반복)
• if문은 마지막 깊이까지 탐색을 마쳤을 때, 빠져나오기 위한 구문이다.
  • 한 가지 길에 대해 탐색을 마쳤으므로 결과를 전역변수에 저장하고 해당 메소드를 종료한다.

http://www.cse.unsw.edu.au/~billw/Justsearch.html

permutate() 메소드를 호출하는 solution() 메소드 예시

public long solution(String expression){
        // 수식으로 DFS를 이용해 순열을 만든다.
        permutate(new boolean[operations.size()],0,new String[operations.size()]);
        }