[백준] 15651번 - N과 M(3) (Java)

 

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

15651번: N과 M (3)

 

<문제 분석>

중복숫자와 순열 모두 허용이다.

N과 M (1)과 (2)에서 중복을 막기 위해 사용했던 visited[]을 사용 안하면 된다.

다만, 출력을 System.out.print()를 하게 되면 시간초과가 난다.

대신 StringBuilder로 문자열을 계속 머지한다음 마지막 한번 출력했더니 통과했다.

 

<코드 구현 #1>

import java.util.Scanner;


//[백준] 15651번 - N과 M(3) (Java)

public class Main {
    static int N, M;
    static int arr[];
    static StringBuilder sb = new StringBuilder();
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        visited = new boolean[N+1];
        arr = new int[M];
    }

    public void dfs(int N, int M, int depth) {
        // 1. 종료조건
        if (depth == M) { // depth가 M가 같아지면 탐색 종료
            for (int x : arr) {
                sb.append(x).append(' ');
            }
            sb.append('\n');
            return;
        }
        // 2. 함수본체
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue; // 중복숫자 방문 방지, 이미 방문한 노드면 패스!
            arr[depth] = i; // depth(0과 1)에 맞게 방문한한 노드 저장
            dfs(N, M, depth+1); // 다음 노드 탐색 시작
        }
    }

	public void Solve() {
        dfs(N, M, 0);
        System.out.println(sb);
	}
    
	public static void main(String[] args)
	{
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<코드구현 #2>

import java.util.Scanner;
import java.lang.StringBuilder;

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

    void inputData(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = new int[M];
        sc.close();
    }

    void DFS(int level) {
        // 종료 조건
        if (level == M) {
            for (int x : A) {
                sb.append(x).append(' ');
            }
            sb.append('\n');
            return;
        }

        // 재귀호출 조건
        // 중복을 허용, 순서 바꾸면 다른 조합으로 인정한다.
        // 방문배열을 사용하지 않는다.
        for (int i=1; i<=N; i++) {
            A[level] = i;
            DFS(level+1);
        }
    }
    
    void Solve() {
        DFS(0);
        System.out.println(sb);
    }
 
    public static void main(String[] args) {
        Main m = new Main();
        m.inputData(); // 입력함수
        m.Solve();
    }
}