[BAEKJOON] 15654 N과 M (5)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • N, M 가 주어 졌을때 1 ~ N수 에서 중복된 숫자가 없고 크기 순으로 출력하면 된다.
  • 중복되는 수열은 여러번 출력하면 안된다.
• 사이트 주소: https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

문제풀이

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

https://jih3508.tistory.com/84

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

접근 방법 

 N과 M 문제 푼 내용 보면  다른 점이 크기 순으로 출력해야 한다는 점이고 중복된 숫자가 없어야 한다. 일단 크기 순으로 출력하는 방법은 수열을 정렬하면고 그대로 백트레킹으로 돌리면 된다. 그리고 중복된 숫자가 없어야 하는 부분은 visited라는 배열을 선언해서 방문한 인덱스를 체크 하면서 진행 하면 위에 답처럼 나올것이다.

1. 방문 체크할 visited 선언한다.
2. 재귀 호출할 함수를 만든다.
   • M까지 도달하면 출력한다.
   • for문으로 0 ~ N - 1까지 돌린다.
   • 인덱스 방문 안했으면 visited배열 인덱스에 체크 하고 재귀 호출 한다.
   • 재귀 호출 하는 부분 끝나면 visitrd배열 인덱스 체크한 부분을 푼다.

Code

Python

def NM(n, arr = []):
    if n == M:
        print(' '.join(map(str, arr)))
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            NM(n + 1, arr + [array[i]])
            visited[i] = False
    
N, M = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
visited = [False] * N
NM(0)

Java

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

public class Main {
	
	static int[] array1, array2;
	static int N, M;
	static StringBuilder sb = new StringBuilder();
	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());
		st = new StringTokenizer(br.readLine());
		array1 = new int[N];
		array2 = new int[M];
		visited = new boolean[N];
		for(int i = 0; i < N; i ++) {
			array1[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(array1);
		NM(0);
		System.out.println(sb);
		
	}
	
	public static void NM(int x) {
		if(x == M) {
			for(int i = 0; i < M; i++) {
				sb.append(array2[i]).append(" ");
			}
			sb.append("\n");
			return;
		}
		for(int i = 0; i < N; i++) {
			if(!visited[i]) {
				visited[i] = true;
				array2[x] = array1[i];
				NM(x + 1);
				visited[i] = false;
			}
		}
		
	}
}