[백준] 15649번 : N과 M (1) (JAVA)

앞에서 백트래킹을 공부한 다음 백준 백트래킹 관련 문제인 15649번 : N과 M (1) 을 풀었다.

 

백트래킹에 대해 아직 이해하지 못했다면 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/3

알고리즘 - 백트래킹(Backtracking)

---

<문제>

 

<문제 해석>

백트래킹을 이용하여 1부터 N까지 중복 없이 M개의 수를 고른 수열을 출력하라.

 

<문제 해결>

1. n과 m을 입력받는다.

 

2. 다음 노드를 탐색하기 위한 boolean 배열 생성 : check

 

3. 탐색과정에서 값을 담을 int 배열 생성 : ar

 

4. 백트래킹 함수

 

 - index가 마지막 위치에 도달하면 수열을 출력하도록 한다.

 - for 문을 이용하여 수열 생성

        if, check 배열에서 해당 수를 사용했다면 다음으로.

 

        해당 수를 사용하면 check 배열에 true 적용

                                     ↓

                   ar에 index위치에 i 넣고,

                                     ↓

            index값 1씩 증가하면서 재귀 진행

                                     ↓

                        check 배열 초기화

 

 

 

<코드>

 

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

public class Main {
	static int n, m;
	static boolean check[]; 
    static int ar[];
	static StringBuilder sb = new StringBuilder();
	
	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());
		
		check = new boolean[n+1];
		ar = new int[n+1];
		
		go(0);
		
		System.out.println(sb);
	}
	
	
	public static void go(int index) {
		
		if(index == m) { 
			for(int i=0; i<m; i++) {
				sb.append(ar[i]).append(" ");
			}
			sb.append('\n');
			return;
		}

		for(int i=1; i<=n; i++) {
			if(check[i]) continue;
			check[i] = true;
			ar[index] = i;
			go(index+1);
			check[i] = false;
		}
	}
}

 

---

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

15649번: N과 M (1)