15650번 N과 M(2)

실버3 - 백트래킹

소스 코드

문제 링크

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

public class Main {
    static int N, M;
    static boolean[] visited;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            visited = new boolean[N];
            arr = new int[M];

            DFS(0);

            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static void DFS(int depth) {
        if (depth == M) {
            if (checkSort()) return;

            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1;
                DFS(depth + 1);
                visited[i] = false;
            }
        }
    }

    private static boolean checkSort() {
        boolean isSort = false;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                isSort = true;
                break;
            }
        }

        return isSort;
    }
}

---

풀이 방법

이전에 풀었던 N과 M(1) 문제의 코드를 그대로 사용하고 조건을 바꿔서 문제를 풀려고 했다.

checkSort() 메서드를 만들어서 오름차순 정렬이 제대로 되었는지 확인! isSort 변수가 true인 경우는 제대로 정렬이 되지 않았다는 의미이다.
(쓰고 보니까 기본을 true로 두고 정렬이 되지 않았을 때 false로 변경하는게 더 좋아 보이긴 한다...)

여튼!! 전체 배열을 확인해서 이전 숫자보다 작은 숫자가 나온 경우 정렬이 틀어졌다고 판단하고 아무것도 출력하지 않고 return 을 해서 조건을 만족 시켰다!

근데 코드를 다 작성하고 보니까... 음... 이렇게 for 문을 사용한 조건은 뭔가 비효율적인 것 같고...

이전에 확인했던 숫자는 확인하지 않고 바로 다음으로 넘어가는게 더 좋아보인다.

결국 다시 다른 사람의 풀이를 보고 코드를 확인했다!!

---

더 간편한 풀이

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

public class Main {
    static int N, M;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            arr = new int[M];

            DFS(1, 0);

            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static void DFS(int at, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = at; i <= N; i++) {
            arr[depth] = i;
            DFS(i + 1, depth + 1);
        }
    }
}

이 코드도 Stranger's LAB님의 블로그에서 확인했다.

DFS를 실행할 때 현재 위치를 알려주는 at 변수를 추가해서 아주 간단하게 해결....!!

나는 이렇게 변수를 추가해서 할 생각은 못하고... 이전에 방문했던 수를 어떻게 제외시켜야 할 지 한참 고민했는데 ㅠㅠ 역시 문제는 많이많이 풀어봐야 한다!!!