[문제풀이] 08-04. 중복 순열

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

DFS, BFS 활용 - 0804. 중복 순열

🗒️ 문제

🎈 나의 풀이

	private static String DFS(int n, int m, String s) {
        for(int i=1; i<=n; i++) {
            String str = s;
            str += i + " ";
            if(m == 1) System.out.println(str);
            else DFS(n, m-1, str);
        }
        return "";
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        DFS(n, m, "");
    }

🖍️ 강의 풀이

  	static int[] pm;
	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=1; i<=n; i++){
				pm[L]=i;
				DFS(L+1);
			}
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		pm=new int[m];
		T.DFS(0);
	}

💬 짚어가기

해당 문제는 DFS를 이용하여 풀 수 있다. N개 자연수의 중복 순열 조합은 $N^2$개 이다.
따라서 나의 풀이에서는 1부터 N까지 반복문을 수행하며 주어진 조합의 크기 m 만큼
재귀 호출을 수행하여 문제를 해결하였다.

강의에서는 마찬가지로 반복문을 수행하며 m 만큼 재귀 호출을 수행하였다. 나는 결과를
문자열에 합치도록 하였고, 강의에서는 배열을 이용하였다.