[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS - 기출문제

DFS, BFS 기출문제 풀이

중복순열 구하기

• 설명 : 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
  
  

• 입력 : 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다.
  
  

• 출력 : 첫 번째 줄에 결과를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
  
  

• 풀이 답안

import java.util.*;

public class Main {

    static int num, cnt;

    public void DFS(int v, int[] arr){
        if(v==cnt) {
            for (int i1 : arr) {
                System.out.print(i1+" ");
            }
            System.out.println();
        } else {
            for(int i=1; i<=num; i++){
                arr[v]=i;
                DFS(v+1, arr);
            }
        }
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        cnt = scan.nextInt();
        int[] arr = new int[cnt];

        main.DFS(0, arr);
    }
}

• 정리
  
  • 이전 DFS는 양 노드를 도는 방식으로 하였다면 이번 문제의 경우 각 노드에서 모든 경우의 수를 돌고
    
  • 그 다음 하위 노드에서 또 모든 경우의 수를 돌도록 구현해야 했음
    
  • 일차원 배열을 만들어 해당 배열을 매개변수로 넘겨주는 방식으로 구현
    
  • 첫번째 접근시 첫 배열값을 정해주고 재귀함수를 돌게함