백준 15649. N과 M(1) :: 돼지개발자

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

"DFS, char[] Array를 사용하자."

순열을 탐색하는 것은 DFS를 통해 쉽다. 그런데 경로를 찍는데 효과적인 방법이 없을까 고민했다. 애초에는 DFS 에 파라미터로 String s 를 하나 더 두어 이를 append 시켜주었지만, N과 M 이 커지면 굉장히 오래 걸릴 것 같았다. String은 immutable 하고, premitive type 도 아니여서 연산이 오래걸린다.

따라서 char[] res 배열을 하나 두어 사용했다. 아주 굳 DFS 탐색 경로를 찍는데 아주 유용할듯 하다.

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    static int N,M;
    static StringBuffer sb = new StringBuffer();
    static boolean[] visited;
    static char[] res;
    
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        visited = new boolean[N+1];
        res = new char[2*M];
        for (int i = 0; i < 2 * M; i++) res[i] = ' ';
        
        solve(0);
        System.out.println(sb.toString());
    }
    
    static void solve(int cnt) {
        if(cnt == M) {
            sb.append(res);
            sb.append("\n");
            return ;
        }
        
        for (int i = 1; i <= N; i++) {
            if(visited[i]) continue;
            
            visited[i] = true;
            res[cnt*2] = (char)(i+'0');
            solve(cnt+1);
            visited[i] = false;
        }
        
    }
 
}