BOJ - N과 M (3)

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

15651번: N과 M (3)

• 단계별 풀어보기 - 백트렉킹 문제이다.
  • https://www.acmicpc.net/step/34 
  • visited을 삭제하면 중복을 허용하여 모든 노드를 탐색 할 수 있다.
  • 하지만 기존 코드에서 노드 리스트에서 대상 삭제 로직이 노드 번호 였는데 중복이 들어오면서 꼬이게 된다.
  • 노드 번호를 기준으로 삭제하는 것이 아닌 탐색이 끝났을 시, 마지막 뒷 노드를 삭제하게 만들었다.

 

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static int N;
    public static int M;

    public static StringBuilder builder = new StringBuilder();

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        ArrayList<Integer> numbers = new ArrayList<>();
        boolean[] visited = new boolean[N + 1];
        dfs(numbers, visited, 0);
        System.out.println(builder);
    }

    private static void dfs(ArrayList<Integer> numbers, boolean[] visited, int depth) {
        if (depth == M) {
            for (Integer no : numbers) {
                builder.append(no + " ");
            }
            builder.append("\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            Integer next = i;
            numbers.add(next);

            dfs(numbers, visited, depth + 1);
            //중복으로 값이 들어가므로 가장 멘 뒤에 노드를 삭제한다.
            numbers.remove(numbers.size() -1);
        }
    }
}