[백준] 15650번 - N과 M(2) (Java)

 

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

15650번: N과 M (2)

 

<문제 분석>

N과 M(1)과 비슷한데 중복 순열을 허용하지 않는 점이 차이가 닌다.
이전 문제는 중복 숫자만 방문배열을 통해서 처리를 했는데 이 문제에서는 순서가 달라도 중복이면 표시하면 안된다.

예제를 보면,
4 2
----
1 2
1 3
1 4
2 3
2 4
3 4
이런 식으로 1로 시작하는 값이 2로 시작하는 순열을 시작할 때 중복체크 락이 걸려있어야 한다.

(1)에서는 재귀 호출에서 돌아오면 중복체크를 풀어줬다.
하지만 (2)에서는 i번까지의 중복체크는 락을 유지해야지 중복순열을 막을 수 있다.

 

따라서 재귀호출에서 돌아올 때 visited[i] = false 해주던 것을 i번째 이후부터 풀어주면 된다.

 

<코드 구현 #1>

import java.util.Scanner;


//[백준] 15650번 - N과 M(2) (Java)

public class Main {
    static int N, M;
    static boolean visited[];
    static int arr[];
    
    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) {
                System.out.print(x+" ");
            }
            System.out.println();
            return;
        }
        // 2. 함수본체
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue; // 중복숫자 방문 방지, 이미 방문한 노드면 패스!
            visited[i] = true;
            arr[depth] = i; // depth(0과 1)에 맞게 방문한한 노드 저장
            dfs(N, M, depth+1); // 다음 노드 탐색 시작
            //visited[i] = false; // N&M(1) 다음 탐색을 위해 방문처리 초기화
            for (int j=i+1; j<=N; j++) { // N&M(2) 중복순열을 막기위해 i번째 이후로 방분배열을 초기화한다.
                visited[j] = false;
            }
        }
    }

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

 

<제출 결과>

 

<코드구현 #2>

import java.util.Scanner;

public class Main {
    static int N, M;
    static int A[];
    static boolean visited[];

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

    void DFS(int start, int level) {
        // 종료 조건
        if (level == M) {
            for (int x : A) {
                System.out.print(x+" ");
            }
            System.out.println();
            return;
        }

        // 재귀호출 조건
        // 중복을 허용하지 않기 위해 완전탐색이 끝난 숫자는 다음에 제외한다.
        for (int i=start; i<=N; i++) {
            if (!visited[i]) { // 아직 선택하지 않은 숫자아면...
                visited[i] = true; // 선택한 숫자는 방문처리
                A[level] = i;
                DFS(i, level+1);
                visited[i] = false;
            }
        }
    }
    
    void Solve() {
        DFS(1, 0);
    }
 
    public static void main(String[] args) {
        Main m = new Main();
        m.inputData(); // 입력함수
        m.Solve();
    }
}