백준 15649번 - N과 M (1) [브루트 포스/자바 JAVA]

https://www.acmicpc.net/problem/15649

 

백준 15649번

 

---

사고방식 

dp를 활용하는 문제이다. 

 

알고리즘 문제들을 풀다보니 dfs로 생각하면 되지 않을까? 하는 생각이 들었고 코드를 짜보았다. 

 

Scanner 사용하여 입력값 두 값을 N, M으로 받아주고, 

visitm arr 배열을 선언한 뒤 

 

이제 depth를 1씩 증가시키며, visit 배열을 통해 방문한 곳은 다시 방문하지 않도록 dfs를 돌려주면 된다. 

 

---

결론 

import java.util.Scanner;

public class Main {
    
    public static boolean [] visit;
    public static int arr [];
    
    public static void main(String args[]) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        visit = new boolean [N];
        arr = new int [M];
        
        dfs(N, M, 0);
        
    }
    public static void dfs(int N, int M, int depth){
            
            if (depth == M){
                for (int val : arr){
                    System.out.print(val + " ");
                }
                System.out.println();
                return;
            }
            
            for (int i=0; i<N; i++){
                if (visit[i]==false){
                    visit[i] = true;
                    arr[depth] = i+1;
                    dfs(N, M, depth+1);
                    visit[i] = false;
                }
            }
        }
}