#15649: N과 M (1) [JAVA]

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

15649번: N과 M (1)

 

 

---

 

 

 

문제 접근

 

 

 

 

nPm을 구하는 문제이다.

 

dfs로 백트래킹을 구현

 

 

 

[ 참고 ]  https://st-lab.tistory.com/114

ㄴ 봐도봐도 이해가 안됐는데.. 보다보니 이해 됨..! 코드의 흐름을 잘 따라가보자

 

 

 

 

 

코드

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {

	static int[] arr; //출력 저장 배열
	static boolean[] visited; 
	static int m;
	static int n;
	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());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[m];
		visited = new boolean[n];

		dfs(0);
		System.out.println(sb);
	}

	public static void dfs(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 (!visited[i]) {
				visited[i] = true;
				arr[depth] = i + 1;
				dfs(depth + 1);
				visited[i] = false;
			}
		}

	}
}

 

 

 

 

n=4, m=2인 경우에 (즉, 4P2를 구하는 경우)

 

dfs의 for문에서 i=0~i=3까지 반복하는데 i는 각각의 노드임. (아래 그림 참고)

 

 

 

for문의 동작 방식을 그림으로 표현하면 다음과 같다.

 

 

x는 visited==true여서 배제된 요소를 의미함.

 

 

 

 

 

참고로 https://chaechaepower.tistory.com/103

 

위 포스팅에서 쓴 바와 같이 순열을 재귀적으로 구현해서 풀어봤으나 문제의 사전 순으로 출력하라는 조건을 만족하지 못해서 통과 못함.