[Algorithm] 완전 탐색 - 순열

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다.

출처 : https://github.com/rhs0266/FastCampus

 

 

완전 탐색

문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다.

 

장점 : 부분 점수를 얻기 좋음

단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음

 

완점 탐색 종류

• N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 
• N개중 중복없이 M개를 순서 있게 나열하기 : 순열
• N개중 중복을 허용하여 M개를 고르기 : 중복조합
• N개중 중복없이 M개를 고르기 : 조합

 

완전 탐색 문제 접근 시

• 고를 수 있는 값의 종류 파악
• 중복 여부
• 순서를 따지는 지

 

N개중 중복없이 M개를 순서 있게 나열하기 : 순열

 

백준 15649) N과 M (1)   https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

1) 아이디어

중복 순열과 마찬가지로 각 자리에서 재귀호출로 다음 자리로 올 수 있는 모든 경우의 수를 탐색하면 된다.

단, 중복을 허용하지 않으므로 선택될 때마다 방문 처리를 해주어 다음 선택지에서 제외될 수 있도록 해준다.

 

 

2) 시간 복잡도 계산

N = 3, M = 2일 때

 

        ___ ___    2 자리를 중복 없이 고르는 거니까 3 * 2 = 3!

 

시간 복잡도 : O(nPm) 

N과 M의 최대 값이 8이니까 8! < 1억(1초)

 

 

3) 구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static boolean[] visit;
    static int[] selected;

    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());

        visit = new boolean[N + 1];
        selected = new int[M + 1];

        rec_func(1);

        bw.close();
    }

    private static void rec_func(int k) throws IOException {
        // 한 케이스 다 골랐으면 출력
        if (k == M + 1) {
            for (int i = 1; i <= M; i++) {
                bw.write(selected[i] + " ");
            }
            bw.write("\n");
        } else {
            for (int i = 1; i <= N; i++) {
                // 중복 체크 
                if(visit[i] == true) continue;

                // 선택 + 방문처리
                selected[k] = i;
                visit[i] = true;

                // 재귀호출로 다음 자리 모든 경우 탐색
                rec_func(k + 1);

                // 고르고 나면 다시 초기화
                selected[k] = 0;
                visit[i] = false;
            }

        }
    }
}