백준 15649번 :: N과 M (1)

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

15649번: N과 M (1)

 

사실,, N과 M (3) 풀어보려고 하다가.. 못 풀고 (1) 내려온거 안비밀..ㅋㅋ

 

1. 백트래킹 이용

2. 백트래킹이란? 재귀 알고리즘에서 배울 수 있었던 것 ~

3. 백트래킹을 이용한 8퀸 문제 풀이로 먼저 공부하고 문제를 해결해보았다.

 

 

▽ 이 코드는 해당 문제 풀이 아니고~ 8퀸 문제 풀이 코드

재귀 호출을 하여 가지를 뻗으며 모든 조합을 나열함 (사실 아직도 완벽히 이해는 안됨..)

class queen {
    public static void main(String[] args) {
        set(0);
    }
    static int N = 4;
    static int[] pos = new int[N];


    static void set(int i) {
        for (int j = 0; j < N; j++) {
            pos[i] = j + 1;
            if (i == N - 1) { // pos 배열의 끝까지 갔다.
                print();      // 배열 다 채웠으니 출력해라
            } else {
                set(i + 1);   // 배열 안채웠으니 인덱스 증가하여 다시 반복해라
            }
        }
    }

    static void print() {
        for (int i = 0; i < N; i++) {
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }
}

 

 

▽ 이 코드가 문제 풀이 코드

public class Main {
 
	public static int[] arr;
	public static boolean[] visit;
	public 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());
 
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
 
		arr = new int[M];
		visit = new boolean[N];
		dfs(N, M, 0);
		System.out.println(sb);
 
	}
 
	public static void dfs(int N, int M, int depth) {
		if (depth == M) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
 
		for (int i = 0; i < N; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i + 1;
				dfs(N, M, depth + 1);
				visit[i] = false;
			}
		}
	}
 
}

사실 코드를 보면 이해가 되는데, 이 코드를 떠올리기까지 과정이.. 아직 너무 힘든 것 같다.

특히 재귀적으로 dfs를 계속 호출해서 쓰는 저 부분이 아직 완벽히 이해는 안되었는데 일단 오늘은 여기까지.. ㅠㅠ