[문제 풀이] 백준 15655번 N과M(6) JAVA

문제

  문제접근 방법   

해당 문제는 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하는 문제로 이때, N개의 자연수는 모두 다른 수이다.

처음에는 이전에 풀었던  N과 M(5)에 풀이 방식에 매몰되어서 방문처리를 했다가 처음 오는 값 즉 1 7일 때 1은 true, 7의 값의 자리에는 방문 false 처리해서 백트래킹해보려고 했지만 결국 방문처리했다가 다시 false처리해 주는 것은 방문처리 없이 문제를 풀이해도 된다는 뜻으로 해석해 아래와 같이 접근하여 문제를 해결하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static int num[];
    public static boolean visited[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        int arr[]=new int[n+1];
        visited=new boolean[n+1];
        num=new int[m];
        
        for(int i=1;i<=n;i++){
            arr[i]=s.nextInt();
        }
        Arrays.sort(arr);
        dfs(0,1,n,m,arr);
    }
    public static void dfs(int depth,int start,int n,int m,int arr[]){
        if(depth==m){
            for(int i=0;i<m;i++){
                System.out.print(num[i]+" ");
                
            }System.out.println();
            return;
        }
        
        for(int i=start;i<=n;i++){
           
                num[depth]=arr[i];
                dfs(depth+1,i+1,n,m,arr);
            
        }
    }
}

만약 1 7 8 9를 입력받았다고 했을 때, 처음 접근 방식은 1이 반복이 되는 동안 1을 제외한 다른 값들은 visited[]=false처리해주고 1만 true처리해서 나중에 반복할 때도 중복 없이 가능하게 해야겠다고 생각했다. 하지만 해당 문제는 N과 M(2)와 굉장히 유사한 문제인데 본문제에서는 1,2,3,4 이런 식이 아닌 입력받은 값으로 제세되어서 처음에 위에 설명한 것처럼 풀이했다 이후 N과 M(2) 문제처럼 중복처리를 해야겠다고 생각해 최종 코드와 같이 작성하여 문제를 해결하였다.

 

  마무리  

DFS를 연습하면서 가장 처음 접한 문제가 N과M 시리즈이다. 1번부터 5번까지 해결하면서 이제는 나름 이해했다고 생각했다.

하지만 6번 문제를 해결하면서 문제의 조건이 살짝만 추가되고 바뀌어도 헛갈리고 dfs에 대한 이해가 부족하다는 것을 느끼었다.

시리즈라고 다 비슷한 문제라고 생각되어 안풀어보고 넘어가려고도 했지만 막상 풀어보니 dfs에 대해 정리하고 이해하는데 큰 도움이 되었다. 

 N과 M 시리즈 

https://hmkang32180116.tistory.com/127

[문제 풀이] 백준 15649번 N과 M(1) JAVA _다시풀이

 

https://hmkang32180116.tistory.com/132

[문제 풀이] 백준 15650번 N과 M(2) JAVA

 

https://hmkang32180116.tistory.com/178

[문제 풀이] 백준 15651번 N과 M(3) JAVA

 

https://hmkang32180116.tistory.com/179

[문제 풀이] 백준 15652번 N과 M (4) JAVA

 

https://hmkang32180116.tistory.com/180

[문제 풀이] 백준 15654번 N과M(5) JAVA