[문제풀이] 08-06. 순열 구하기

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0806. 순열 구하기

🗒️ 문제

🎈 나의 풀이

	private static int[] ch;
    private static void DFS(int m, int[]arr, String s) {
        for(int i=0; i< arr.length; i++) {
            if(ch[i] == 0) {
                String str = s;
                str += arr[i] + " ";

                if (m == 1) System.out.println(str);
                else {
                    ch[i] = 1;
                    DFS(m-1, arr, str);
                    ch[i] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        ch = new int[n];

        for(int i=0; i<n; i++) arr[i] = sc.nextInt();

        DFS(m, arr, "");
    }

🖍️ 강의 풀이

  	static int[] pm, ch, arr;
	static int n, m;
	public void DFS(int L){
		if(L==m){
			for(int x : pm) System.out.print(x+" ");
			System.out.println();
		}
		else{
			for(int i=0; i<n; i++){
				if(ch[i]==0){
					ch[i]=1;
					pm[L]=arr[i];
					DFS(L+1);
					ch[i]=0;
				}
			}
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		arr=new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		ch=new int[n];
		pm=new int[m];
		T.DFS(0);
	}

💬 짚어가기

해당 문제는 DFS를 이용하여 풀 수 있다. 나의 풀이의 경우 해당 자연수의 사용 여부를
결정하는 배열을 생성하였다. 반복문을 통해 자연수가 담긴 배열을 순회하고, 해당 자연수를
문자열에 추가한 후 파라미터로 넘기는 방식으로 재귀 호출을 수행하였다.

재귀 호출에서 이미 사용한 자연수를 제외한 나머지 자연수를 반복문을 통해 사용하고, 이를
주어진 순열의 크기 만큼 반복하여 문제를 해결한다.

강의에서도 동일한 로직으로 수행하였다. 다만 문자열이 아닌 배열에 담아 전달하는 방식으로
문제를 해결하였다.