BOJ - N과 M (1)

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

15649번: N과 M (1)

 

시간 초과 ㅠㅠ 머리 아프다

 

• 단계별 풀어보기 - 백트렉킹 문제이다.
  • https://www.acmicpc.net/step/34 
  • 시간초과가 엄청나게 나서 자바에서 최적화 관련으로 열심히 뒤져서 겨우 통과 했다.
• 최적화 단계
  • DFS 함수 콜 3 -> 2 으로 변경
  • System.out.printf -> System.out.print 변경
  • System.out.print -> StringBuilder 마지막 한번 출력으로 변경
• 통과 코드

    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++) {
                if (visited[i] == false) {
                    Integer next = i;
                    visited[i] = true;
                    numbers.add(next);

                    dfs(numbers, visited, depth + 1);
                    visited[next] = false;
                    numbers.remove(next);
                }
            }
        }
    }

 

• 시간 초과 났던 처음에 만든 코드

import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

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

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        dfs(N, M);
    }

    private static void dfs(int n, int m) {
        for (int i = 1; i <= n; i++) {
            ArrayList<Integer> numbers = new ArrayList<>();
            boolean[] visited = new boolean[n + 1];
            dfs(i, n, m, numbers, visited, 0);
        }
    }

    private static void dfs(int current, int n, int m, ArrayList<Integer> numbers, boolean[] visited, int depth) {
        if (depth == m) {
            return;
        }

        if (visited[current] == true) return;

        Integer number = current;
        visited[current] = true;
        numbers.add(number);

        if(numbers.size() == m) {
            for(Integer no : numbers) {
                System.out.printf("%d ", no);
            }
            System.out.println();
        }

        for (int i = 1; i <= n; i++) {
            if (visited[i] == true) continue;
            dfs(i, n, m, numbers, visited, depth + 1);
        }
        visited[current] = false;
        numbers.remove(number);
    }
}