[백준 15649] N과 M(1) - JAVA - [DFS]

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 15649

"N과 M (1)" 포스팅입니다.

 

15649번: N과 M (1)

수열을 구해주면 되는데

사전순으로 증가하게 출력해야합니다.

파이썬을 쓰면 그냥 구현이 되어 있다라고 하더라구요

하지만 자바를 사용하기 떄문에 구현해주어야합니다.

DFS로 구현해줍니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main{
    public static int[] arr;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();

    public static void dfs(int n, int m, int depth){
        //m개의 갯수만큼 뽑힌거임
        if(depth == m){
            for( int i : arr){
                sb.append(i).append(' ');
            }
            sb.append('\n');
            return;
        }
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = i+1;
                dfs(n,m,depth+1);
                visited[i] = false;
            }
        }
    }
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        visited = new boolean[n];
        dfs(n,m,0);
        System.out.println(sb);
    }
}

DFS 구현으로

for(int i=0; i<n; i++){
    if(!visited[i]){
        visited[i] = true;
        arr[depth] = i+1;
        dfs(n,m,depth+1);
        visited[i] = false;
    }
}

이 부분이 핵심입니다.

 

예시를 들자면 일단 depth는 뽑아야하는 갯수입니다.

4개 중 2개를 뽑아야한다면

-> depth는 2가 되겠죠

 

1을 탐색하고 -> 2를 탐색하고 depth가 되었으니 1,2출력

그 후 2는 true이니깐 3 탐색해서 1,3 이렇게 계속 출력이 되고

다 탐색을 한 후에는 false로 다시 탐색 할 수 있도록 해줍니다.

2 1 이렇게 탐색을 해야하기 떄문에