[백준] 15649번 - N과M(1) (Java)

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

 

 

15649번: N과 M (1)

 

15649번: N과 M (1)

 

<문제 분석>

중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다.
dfs탐색을 사용한 백트레킹 알고리즘으로 풀자.

백트레킹은 탐색할 노드를 조건문으로 판단하여 유망하면 더 탐색하고, 아니면 그만두고 돌아온다.
이것이 완전탐색을 하는 부르트포스와의 차이점이다.

<풀이>
dfs 파라메터로는 N과 M, 그리고 depth를 넘겨준다.
depth는 dfs가 호출될 때마다 +1씩 해준다.
depth == M이되면 담았던 값들을 출력하고 다음 탐색을 위해 돌아간다.
중복 숫자 체크는 방문배열로 한다.
출력은 재귀함수 종료조건에서 그 사이클에 해당하는 값들을 출력한다.

a. 재귀 종료 조건
  - if (depth == M)이면 저장한 값 출력하고 종료

b. 재귀함수 본체
  - for i = 1 to N 반복
  - visited[i]가 false이면 처리 시작
  - i 노드의 방문 처리를 하고 arr[depth] = i (노드값)을 저장
  - 다음 탐색을 위해 dfs(index+1) 호출될

 

<코드 구현 #1>

import java.util.Scanner;


//[백준] 15649번 - N과M(1) (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; // 다음 탐색을 위해 방문처리 초기화
        }
    }

	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 level) {
        // 종료 조건
        if (level == M) {
            for (int x : A) {
                System.out.print(x+" ");
            }
            System.out.println();
            return;
        }

        // 재귀호출 조건
        for (int i=1; i<=N; i++) {
            if (!visited[i]) { // 아직 선택하지 않은 숫자아면...
                visited[i] = true; // 선택한 숫자는 방문처리
                A[level] = i;
                DFS(level+1);
                visited[i] = false;
            }
        }
    }
    
    void Solve() {
        DFS(0);
    }
 
    public static void main(String[] args) {
        Main m = new Main();
        m.inputData(); // 입력함수
        m.Solve();
    }
}