백준 자바 문제풀이 #15651

문제 링크

N과 M (3)

유사 문제를 많이 풀어서 그런가 어렵지 않게 풀었다.

DFS로 해결했고, 정답을 담을 배열을 별도로 마련해 출력했다.

코드(성공)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] visited;
    static int[] answer;
    static int n, m;
    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());

        visited = new int[n + 1];
        answer = new int[n + 1];
        DFS(1);
        System.out.println(sb);
    }

    static void DFS(int depth){
        if (depth == m + 1) {
            print();
            return;
        }

        for (int i = 1; i <= n; i++) {
            visited[i]++;
            answer[depth] = i;
            DFS(depth + 1);
            visited[i]--;
        }
    }

    static void print(){
        for (int i = 1; i <= n; i++) {
            if (answer[i] > 0) {
                sb.append(answer[i]).append(" ");
            }
        }
        sb.append("\n");
    }
}

자바 11 65452 KB 420 ms

---

마무리하려다가 다른분의 풀이를 보게 되었는데

내가 놓친 부분이 있었다.

참고 풀이

이전 방법과 비슷하게 풀다보니

방문여부를 확인하는 visited 배열도 그대로 사용했는데

블로그 글 쓰면서 보니, 정작 visited를 사용하지 않았다.

조금 더 고쳐봤다.

코드(개선)

package Silver.S3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class S15651 {
    static int[] answer;
    static int n, m;
    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());

        answer = new int[m + 1];
        DFS(1);
        System.out.println(sb);
    }

    static void DFS(int depth){
        if (depth == m + 1) {
            print();
            return;
        }

        for (int i = 1; i <= n; i++) {
            answer[depth] = i;
            DFS(depth + 1);
        }
    }

    static void print(){
        for (int i = 1; i <= m; i++) {
            sb.append(answer[i]).append(" ");
        }
        sb.append("\n");
    }
}

자바 11 65568 KB 404 ms

시간이 조금 더 줄어들었다.