백준 15649번 : N과 M(1) (JAVA) 문제 풀이

www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

 

 

이번 문제는 백트래킹 단계의 입문 문제 이다.

 

백트래킹 문제는, 트리 형태의 노드들을 깊이 우선 탐색 (DFS) 을 수행하면서, 노드의 유망성을 판단하여, 유망하지 못하다고 생각하면 가지치기를 하고(풀이시간 단축), 다시 부모 노드로 돌아가서 다른 자식 노드를 탐색하는 방식이다.

 

 

문제 풀이

 

dfs의 기본 틀은 아래와 같다.

 

재귀를 끝낼 조건을 정해줘야 하는데, index가 M이랑 같을 시점에 arr 배열의 모든 원소를 출력해주면 된다.

// 재귀를 끝낼 조건
if(index == M) {
	for(int i=0; i<M; i++) {
    	System.out.print(arr[i] + " ");
    }
    System.out.println();
    return ;
}

 

실행 시 고려해야 할 점.

• 해당 i가 사용 했는지에 대한 여부
  • 만약 사용 안했다면, arr[index] = i; 를 넣어주고,  isUsed[i] 의 사용여부를 체크 해 준다.
  • 그리고 다시 재귀 호출을 해준다.
  • 여기서 주의해야 할 점은, 재귀 호출이 다 끝나고 나면 다시 isUsed[i]를 false로 바꿔주도록 한다.

for(int i=1; i<=N; i++) {
	if( !isUsed[i] ) {
    	arr[index] = i;
        isUsed[i] = true;
        dfs(index + 1);
        isUsed[i] = false;
    }
}

 

 

 

전체 코드

package Baekjoon;

import java.util.*;

public class BOJ_15694 {
    static int N, M;
    static int[] arr;
    static boolean[] isUsed;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        isUsed = new boolean[N + 1];
        arr = new int[M + 1];

        recursion(0);
    }

    private static void recursion(int idx) {
        if (idx == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (!isUsed[i]) {
                isUsed[i] = true;
                arr[idx] = i;
                recursion(idx + 1); // arr의 인덱스를 +1 시켜준다.
                isUsed[i] = false;
            }
        }
    }
}

 

실행 과정