[BAEKJOON] 15649 N과 M (1)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • N, M 가 주어 졌을때 1 ~ N수 에서 중복되지 않는 M개를 순서대로 뽑을때
  • 나올수 있는 수를 모두 출력해라.
• 사이트 주소: https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

문제풀이

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

https://jih3508.tistory.com/84

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

 1 ~ N 까지 수에서 M개를 뽑아 순열로 표현하는 문제이다. 순열을 첫번째 나오는 수부터 M번째 나오는 수를 순서대로 하는 거라서 무작위로 나올수 있는 경우수랑 다르게 표현해야 하기 때문에 백트레킹으로 접근한다면 재귀 호출할때 이전 현재의 값이 이전 배열값이 들어갈 경우에는 리턴 시키는 방법을 써야 한다. 안그려면 모든 경우의 수를 출력해서 배열안에 같은 있는지 체크하기에는 시간 뿐만 아니라 불필요한 메모리까지 사용하게 된다.

 파이썬에서는 백트레킹으로 하는법 말고 itertools 패키지 안에 permutations 함수를 제공해서 백트레킹을 구현하는것 보다는 간편하게 작성을 할수가 있다.

1. N, M을 설정한다.
2. 파이썬은 값을 담을 리스트만 선언하고 그  외의 언어는 값을 담을 배열로 선언하고 visited 배열을 선언한다.
3. 0부터 시작해서 M까지 재귀 호출할 함수를 만든다.
4. M까지 갔을 경우 값을 담은 배열/리스트를 출력한다.
5. 그 외 경우 1 ~ N까지 돌려서 이전에 값을 담을 배열중이나 visited에 값이 존재할 경우는 pass한다.
6. 아닌 경우 visited 는 방문 처리하고 값을  추가하고 함수 재호출한다. 재호출 끝나고난 그 다음 visited는 false 처리한다.

Code

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static StringBuilder sb = new StringBuilder();
	static int[] array;
	static boolean[] visited;
	
	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());
		
		array = new int[M];
		
		visited = new boolean[N+1];

		
		NM(0);
		System.out.println(sb);
	}
	
	public static void NM(int m) {		
		if (m == M){
			for (int i = 0; i < M; i ++) {
				sb.append(array[i] + " ");
			}
			sb.append("\n");
		}else {
			for(int i = 1; i <= N; i++){
                int compareNum = i;
                if(!Arrays.stream(array).anyMatch(Number -> Number == compareNum)){
                    array[Depth] = i;
                    NM(Depth + 1);
                    array[Depth] = 0;
                }
            }
		}
				
	}
	
}

Python

Backtracking

def NM(m, array):
    if m == M:
        print(' '.join(map(str, array)))
    else:
        for k in range(1, N + 1):
            if k not in array:
                NM(m + 1, array + [k])

N, M = map(int, input().split())
NM(0, [])

permutation 사용시

from itertools import permutations

N, M = map(int, input().split())

array = [i for i in range(1, N + 1)]
for item in permutations(array, M):
    print(' '. join(map(str, item)))