자바 알고리즘 - 순열

순열

• n개 중 r개를 순서를 고려하여 뽑기
  ex ) 1,2 두 개의 배열 중 2개를 뽑는 경우 [1,2]와 [2,1]을 다르게 처리

🙀 개인적으로 알고리즘 지식이 부족해서 그런지 코드 돌아가는 구조 자체를 이해하는데 오래 걸렸다. 나중에 다시 볼려고 코드를 한 줄씩 분석 해 볼 것.

코드

public class Permutation {

    public static void main(String[] args){
         int arr[] = {1,2,3}
         int output[] = new int[arr.length];
         boolean visited[] = new boolean[arr.length];

         
             perm(arr,output,visited,0,2);
         }

         public static void perm(int arr[], int output[], boolean visited[], int depth, int r){
             if(depth == r){
                 for(int i=0; i<r; i++){
                     System.out.print(output[i]+" ");
                 }
                 System.out.println();
                 return;
             }
             for(int i=0; i<arr.length; i++){
                 if(!visited[i]){
                     visited[i] = true;
                     output[depth] = arr[i];
                     perm(arr,output,visited,depth+1,2);
                     visited[i] = false;
                 }
             }
        }
    }

perm(arr,output,visited,0,2)

• 재귀 함수 시작 시 depth의 값을 0으로 지정하고 r은 2이기 때문에 if문은 패스하고 바로 for문으로 들어간다.

depth : 0, i: 0

• visited 배열이 모두 false로 초기값이 설정되어 있기 때문에 if(!visited[0])은 true 처리 된다.
• i=0에 방문했다는 뜻으로 visited[0]의 값을 true로 바꾼다. (visitied[] = {true,false,false,false})
• 코드 대로 output[depth = 0] = arr[0]
• depth 값에 +1 해주고 재귀 호출 한다.
• perm(arr,output,visited,1,2)

  • depth : 1, r=2 이기 때문에 if 문은 패스한다.
  • depth : 1, i=0 : for문 안으로 들어와 i=0부터 시작하지만 위에서 visited[0]의 값을 true로 바꿔주었기 때문에 if(!visited[0])은 false로 처리 되므로 pass
    depth : 1, i=1 :i=1의 경우 visited[1]의 값을 true로 바꿔주고 output[depth = 1] = arr[1] (visitied[] = {true,true,false,false})
  • 다시 depth + 1 해주고 재귀 호출
  • perm(arr,out,visited,2,2)

    • depth == r 이기 때문에 if문을 실행한다.
    • print문을 실행시켜 output 배열을 출력한다. --> 1 2 출력
    • return을 통해 함수를 빠져나온다.

  • `빠져나오면 depth : 1, i=1로 돌아오므로 visited[1]의 값을 다시 false로 바꿔준다. (visitied[] = {true,false,false,false})
  • depth : 1, i=2: for문에서 i+1 되므로 i=2 --> if(!visited[2])는 true 이므로 visited[2] = true가 되고 output[depth = 1] = arr[2] (perm(arr,output,visited,1,2) 함수 안에서 i값 + 1 된 것임) (visitied[] = {true,false,true,false})
  • 다시 depth + 1 해주고 재귀 호출
  • perm(arr,out,visited,2,2)

    • depth == r 이기 때문에 if문 실행 -> output 배열 1 3 출력

  • return 통해 함수를 빠져 나와 depth : 1, i=2 --> visited[2]의 값을 false로 바꿔준다. (visitied[] = {true,false,false,false})
  • perm(arr,output,visited,1,2) 함수가 for문을 다 돌았으므로
    맨 처음 동작했던 perm(arr,output,visited,0,2)함수로 돌아와 마지막 줄 실행 .

• 맨 위에서 true로 바꿨던 visited[0]의 값을 false로 바꾼다. --> visited[] = [false,false,false,false]
• perm(arr,output,visited,0,2) 함수의 for문에서 i=0일 때의 한바퀴가 끝난 것이므로 i+1 해주고 다시 시작한다.
• perm(arr,output,visited,0,2)
• depth : 0, i=1 ~ 위에서 했던 거 다시 반복 (앞자리 2인 case를 같은 방법으로 도는 것 )