[BAEKJOON]15663 N과 M (9)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • 같은 수를 여러 번 골라도 된다.
  • 길이가  M개의 수열을 예제와 같이 중복없이 사전순으로 출력해라.
• 사이트 주소: https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

접근 방법 

  이번에 출력순서가 아래봐 같다.

1. 배열의 인덱스는 동일하지 않게 출력
2. 수열의 결과들은 중복없게 출력

2가지 조건을 만족해야 한다. 조건 1번은 visited나 checked 배열/리스트를 만들어서 재귀 호출시 방문 여부를 체크하고 방문 안했으면 수열에 저장한 뒤 방문 체크를 한다. 그리고 중복없게 출력을 하는 부분은 수열의 결과가 나올때마다 저장하는데 수열의 결과들을 저장하는 부분에서 없는 경우에만 저장해서 출력하면된다. 

def NM(x, p =[]):
    if(len(p) == M):
        if p not in set_list:
            set_list.append(p)
        return
    for i in range(N):
        if i != x:
            NM(i, p + [array[i]])
        
N, M = map(int, input().split())
array = sorted(list(map(int, input().split())))
set_list = []
NM(-1)
for arr in set_list:
    print(' '.join(map(str, arr)))

 하지만 위 코드 처럼 list 안에 포함 되었는지를 체크 하면 시간 초과가 나올것이다. 그 이유는 리스트가 포함 되어 있는지 아닌지 O(N^2)이 나오기 때문에 포함 되어 있는지 여부를 시간을 최소화 하기 위해서는 set으로 저장해야 하는데 각 언어마다 배열이 리스트를 저장하기에는 힘들어서 결과를 문자열로 변환하다음 set에 다가 저장하면된다. 그러면 비교하는 시간이 O(1)이 나온다.

정리

1. 배열 또는 리스트를 정렬하고 방문여부를 확인하는 배열/리스트를 선언한다.
2.  재귀 호출을 하기전에 각 인덱스 방문여부를 체크하고 방문 안했으면 수열에 저장과 동시에 방문을 체크하고 재귀호출이 끝나면 방문 여부를 false한다.
3. 수열 결과가 나오면 수열 결과들을 저장한 부분에서 결과가 없으면 결과를 저장하고 출력한다.

Code

Python

def NM(p =[]):
    if(len(p) == M):
        string = ' '.join(map(str, p))
        if string not in set_list:
            print(string)
            set_list.add(string)
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            NM(p + [array[i]])
            visited[i] = False
        
N, M = map(int, input().split())
array = sorted(list(map(int, input().split())))
visited = [False] * N
set_list = set({})
NM()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
		
	static int[] array, result;
	static int N, M;
	static Set<String> set = new HashSet<String>();
	static StringBuilder sb = new StringBuilder();
	static boolean[] checked;
	
	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());
		st = new StringTokenizer(br.readLine());
		array = new int[N];
		result = new int[M];
		checked = new boolean[N];
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(array);
		
		NM(0);
		System.out.println(sb);
	}
	
	public static void NM(int k) {
		StringBuilder NMsb = new StringBuilder();
		if (k == M) {
			for(int i = 0; i < M; i++) {
				NMsb.append(result[i]).append(" ");
			}
			if(!set.contains(NMsb.toString())) {
				sb.append(NMsb).append("\n");
				set.add(NMsb.toString());
			}
			return ;
		} 
		
		for(int i = 0; i < N; i++) {
			if(!checked[i]) {
				checked[i] = true;
				result[k] = array[i];
				NM(k + 1);
				checked[i] = false;
			}
		}
	}

}