[BOJ] 15649: N과 M(1) (JAVA)

문제

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

 

여담

DFS & 재귀에 약해서 살짝 헷갈렸다. 관련 문제들이 많은데 풀어보면서 좀 익혀야 할 듯!

 

풀이

DFS와 백트래킹을 사용해서 풀이하면 된다. 이때, 같은 수는 두 번 사용할 수 없으므로 used 배열을 추가해서 해당 수의 사용 여부를 기록해야 한다. 

 

각 수에 대해 탐색을 수행한 뒤, 사용 처리를 취소하지 않으면 해당 수를 더 이상 사용할 수 없다. 즉, 모든 경우의 수를 다 탐색할 수 없다.

 

따라서 탐색이 끝나면 사용했던 수의 사용 처리를 무조건 취소(used[i] = false)해야 한다. 

 

코드

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

public class Main {
    static int N, M;
    static boolean[] used;
    static int[] answer;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        used = new boolean[N + 1];
        answer = new int[M];
        dfs(0);
        System.out.println(sb.toString());
    }

    public static void dfs(int depth) {
        if (depth == M) {
            for (int a : answer) {
                sb.append(a).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (!used[i]) { // 아직 사용하지 않았다면
                used[i] = true; // 사용 처리
                answer[depth] = i; // 해당 자리에 값 기록 
                dfs(depth + 1); // DFS 탐색
                used[i] = false; // 탐색 후, 사용 처리 취소 (백트래킹)
            }
        }
    }
}

---