2022.06.23 백준 Q15649

학습 내용 : 재귀함수를 이용한 순열 알고리즘 생성

이 문제는 순열과 재귀함수를 이용해 수열을 구하는 문제이다. 깊이를 사용해 현재 자신의 몇번째 자리인지 찾고 그 앞에 이미 1~N까지 돌면서 앞자리에 없는 수만 arr[deep]에 넣는다. 그 이후 재귀함수를 이용해 deep을 하나 늘려서 다시 함수를 호출한다(MakeSequence(n,m,a+1). 만약 deep(a로 표현)이 m과 같아지면 arr에 있는 값들이 출력되게 코드를 만들었다. arr의 a앞의 인덱스와 비교를 하기 때문에 따로 출력이 완료되고 값을 초기화해줄 필요가 없다. 

 

 

-내가 처음 짠 코드-

package BaekJoon15649;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        String[] ss = s.split(" ");
        int n = Integer.parseInt(ss[0]);
        int m = Integer.parseInt(ss[1]);
        arr = new int[m];
        MakeSequence(n,m,0);
    }
    static void MakeSequence(int n,int m,int a){
        if(a==m){
            for(int i=0;i<m-1;i++) System.out.print(arr[i]+" ");
            System.out.println(arr[m-1]);
            return;
        }
        all: for(int i=1;i<=n;i++){
            for(int j=0;j<a;j++){
                if(arr[j]==i) continue all;
            }
            arr[a]=i;
            MakeSequence(n,m,a+1);
        }
    }
}

 

 

all: for(int i=1;i<=n;i++){
    for(int j=0;j<a;j++){
        if(arr[j]==i) continue all;
    }
    arr[a]=i;
    MakeSequence(n,m,a+1);
}

아래 내용에서 for(int j=0;j<a;j++)에서 같은 값이 존재한다면 그 밖에 있는 for(int i=1;i<=n;i++)의 반복문에서 continue를 해야하기 때문에 label을 사용해 반복문을 빠져나갔다.

 

 

처음 코드를 짤때는 deep(a로 표현) 전의 인덱스와 비교를 하기 위해 반복문을 사용했는데 visited배열을 통해 해당 숫자가 사용됐는지 확인해서 visit하면 continue 시키는 방법도 좋은 것 같아 다시 작성해보았다. 

 

-새로 작성한 코드-

package BaekJoon15649;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class MakeSequence2 {
    static int[] arr;
    static boolean[] isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        String[] ss = s.split(" ");
        int n = Integer.parseInt(ss[0]);
        int m = Integer.parseInt(ss[1]);
        arr = new int[m];
        isVisited = new boolean[n];
        MakeSequence(n,m,0);
    }
    static void MakeSequence(int n,int m,int a){
        if(a==m){
            for(int i=0;i<m-1;i++) System.out.print(arr[i]+" ");
            System.out.println(arr[m-1]);
            return;
        }
        for(int i=1;i<=n;i++){
            if(isVisited[i-1]) continue;
            arr[a]=i;
            isVisited[i-1]=true;
            MakeSequence(n, m, a + 1);
            isVisited[i-1]=false;
        }
    }
}

 

isVisited배열은 false로 시작하기 때문에 만약 값이 들어갔다면 true로 바꿔주고 deep을 하나 늘려준다 그 후 다 완료했으면 다시 반복문을 돌려야하기 때문에 false로 바꿔준다

 

아래부터 MakeSequence를 f로 간소화시켰다

f(3,2,0) -> arr[0]=1, isVisited[1-1]=true, f(3,2,1)호출

-->f(3,2,1) -> arr[1]=1(isVisited true, continue), arr[1]=2 isVisited[2-1]=true, f(3,2,2)호출

--->---->f(3,2,2)->a==m이므로 1 2 출력 return

--->f(3,2,1)에서 isVisited[2-1]을 사용했으므로 false로 바꿔준다->arr[1]=3 isVisited[3-1]=true, f(3,2,2)호출

이런식으로 동작한다.