2021_summer_모각코] LIE 또! 팀 - 5차시 결과

15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

import java.util.*;
import java.io.*;

public class Main {
	public static int[] arr;
	public static boolean[] check;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();

		arr = new int[m];
		check = new boolean[n];
		ser(n, m, 0);

	}

	public static void ser(int n, int m, int len) {
		if (len == m) {
			for (int war : arr) {
				System.out.print(war + " ");
			}
			System.out.println();
			return;
		}
		
		for (int i = 0; i < n; i++) {
			if (!check[i]) {
				check[i] = true;
				arr[len] = i + 1;
				ser(n, m, len+1);
				check[i] = false;
			}
		}

	}
}

 

backtraking 문제를 처음 접하여 쉬울것 같아서 문제를 골라 보았으나 ,, dfs bfs 를 모른 상태로 문제를 풀려고 하니 어려움이 많았습니다.

 

다음 차시에 bfs dfs를 계획했었는데 순서를 바꿨으면 좀 더 수월하게 풀지 않았었나 생각이 듭니다.

 

아무튼 각설하고 backtracking 문제를 풀어 보았는데 생각 보다 많이 어렵다고 느껴졌습니다.

 

문제를 푸는데도 시간이 오래걸렸고, 재귀 사용을 바로 떠올리지 못해 아직 코딩실력이 많이 부족함을 느낍니다.

 

위 문제를 풀고 n - queen 문제를 풀려고 했으나 시간 부족으로 풀지 못했습니다. 다음 차시 까지 퀸 문제를 포함하여 복습겸 여러 문제를 더 풀어야겠다는 생각이 듭니다...

 

// 백트레킹의 기본 개념 , 백준 자바 풀이