[자바] 백준 15649번 N과 M (1)

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

 

백트래킹 문제였는데, dfs로 풀면 됐다. 사실 dfs 구현하는 것도 까먹어서 다른 사람들 코드를 참고해야했지만.. 

n은 방문할 노드의 개수, m은 방문하는 깊이에 대한 값이라고 생각하면 됐다.

visit 배열을 통해 방문 여부를 체크하여 중복 방문하지 않도록 했다. 내일은.. 다른 사람 코드의 도움 없이 백트래킹 혼자 풀어보자!!!

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static int[] arr;
    public static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        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());

        // 3,1 들어오면 한 줄에 1개만 출력
        // 4,2 들어오면 한 줄에 2개씩 출력
        arr = new int[m];
        // 노드에 대해 방문했는지 확인하기 위해
        // 3,1 들어오면 3개의 노드에 대해 방문여부 체크
        visit = new boolean[n];
        dfs(n, m, 0);

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
    }

    public static void dfs(int n, int m, int depth){
        if(depth == m){
            for(int a : arr){
                sb.append(a).append(' ');
            }
            sb.append("\n");
            return;
        }
        for(int i = 0; i < n; i++){
            if(!visit[i]){ // 만약 노드를 방문하지 않았다면 -> 중복되는 수는 방문할 필요 없음
                visit[i] = true; // 방문 후, true로 바꾸고
                arr[depth] = i + 1; // depth 인덱스에 i+1 저장
                dfs(n , m, depth+1); // 자식 노드 방문 -> 방문하지 않은 경우에 대해서만 재귀 호출
                visit[i] = false; // 자식 노드 방문 후, 다시 방문하지 않은 상태로 변경
            }
        }
    }
}