• 문제 링크: https://www.acmicpc.net/problem/15649
• 참고: https://st-lab.tistory.com/114

설명

아래 상황에서 문제를 어떻게 풀지 이해하여 보겠다.

"a + b + c + d = 20 을 만족하는 두 수를 모두 찾아내시오.
(0 <= a, b, c, d < 100)"

• 브루트포스
  • 모든 경우의 수를 찾아보는 것
  • a=1, b=1, c=1, d=1 부터 a=100, b=100, c=100, d=100 까지 100^4개의 경우의 수를 찾으며, a + b + c + d = 20을 만족하는 값을 찾는다.
  • 모든 경우의 수를 탐색하므로 만족하는 값을 100% 찾는다.
  • 조합 가능한 경우의 수가 많으면, 자원을 매우 많이 필요로 한다.
• 백트래킹
  • a > 20, b > 20, c > 20, d > 20 일 경우 탐색하지 않는다.
  • 탐색하는데 필요한 자원을 줄일 수 있다.
• DFS
  • 백트래킹에 사용하는 탐색 알고리즘의 하나이다.
  • 깊이를 우선으로 탐색한다.

DFS를 사용하여 구현한다.

• 깊이가 같은지 판단하고 같으면 출력한다.
• 0부터 시작하여, 1부터 N까지 돌면서 방문여부를 확인한다.
  • 방문하지 않았다면 출력 배열에 넣고, 방문 여부를 체크한다.
  • 재귀적으로 다음 자식 노드에 숫자를 넣는다.
  • 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경한다.

코드

public class Main {
	static int N, M; 
    static int[] arr;
    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());
        
        arr = new int[M];
        visited = new boolean[N];
        
        dfs(N, M, 0);
	}
    
    private static void dfs(int N, int M, int depth) {
    	if(depth == M) {
        	for(int i = 0; i < M; i++) {
            	System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for(int i = 0; i < N; i++) {
        	if (!visited[i]){
            	arr[depth] = i + 1;
                visited[i] = true;
                dfs(N, M, depth + 1);
                visited[i] = false;
			}
		}
	}        
}