117. 15649( N과M(1) )

import java.util.*;

class Main {
	static int[] tmp;
	static boolean[] visited;

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

		int N = sc.nextInt();
		int M = sc.nextInt();

		sc.close();

		tmp = 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 val : tmp) {
				System.out.printf(val + " ");
			}
			System.out.println();
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				tmp[depth] = i + 1;
				DFS(N, M, depth + 1);
				visited[i] = false;
			}
		}
	}
}

문제요약

DFS를 이용하여 백트래킹을 해보아라.

설명

DFS와 백트래킹에 대한 개념은 아래를 참고하자.

https://smhope.tistory.com/309

백트래킹

https://smhope.tistory.com/307

깊이 우선 탐색(DFS)

간단히 설명하면

N까지 탐색 후 출력하는 문제이다.

 

4 2가 들어왔을 경우를 예를 들어 보겠다.

깊이는 2까지 탐색을 하고 숫자는 1~4가 있는 것이다.

 

그러면 먼저 0에서 1을 탐색하고, 깊이가 2이기 때문에 1, 2 를 출력한다.

0에서 2를 탐색하고 1, 3을 출력한다.

0에서 3을 탐색하고 1, 4를 출력한다.

 

다시 한번 설명하면

0 에서 1을 탐색하면 어느 공간에 1 , 0이 저장되어있다.

깊이가 2이므로 더 이상의 탐색은 끝내고 1을 내 뱉으며 0으로 돌아간다.

다음은 0 에서 2를 탐색한다.

그러면 어느 공간에 2 , 0이 저장된다.

깊이가 2이므로 더 이상의 탐색은 끝내고 2를 내 뱉으며 0으로 돌아간다.

 

즉, 스택(FILO 선입후출) 형태로 로직이 진행되는 것이다.

 

위 과정을 그림으로 설명하면,

이런식으로 진행된다.

코드가 작동하는 것을 그리면

다음과 같이 진행된다.

            visited[i] = False

이 구문이 있기 때문에 백트래킹이 발생하는 것이며, 이 구문이 없다면 1회 방문 후 종료가 된다.