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

www.acmicpc.net/problem/15649

유명한 순열과 조합문제시리즈인 N과 M의 첫번째 문제이다.

순열과 조합은 알고리즘 문제 풀이의 기본 중의 기본이라고 할 수 있고 그렇기때문에 이 N과 M 시리즈는 꼭 풀어보는 것을 추천한다.

순열과 조합에는 어느정도 템플릿이 존재하고, 코드 흐름에 대해 이해한다면 그 다음에는 이것을 사용해야하는 순간에 머리보다 손이 먼저 칠 수 있을정도로 암기할 수 있어야한다고 생각한다.

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

public class Main {

	public static void dfs(int depth, int N, int M, int[] numarray, boolean[] visit) {

		if (depth == M) {
			for (int i : numarray)
			{
				System.out.println(i);
			}
			return;
		}

		for (int i = 0; i < N; i++) {
			if (visit[i]) {
				continue;
			}
			numarray[depth] = i+1;
			visit[i] = true;
			dfs(depth + 1, N, M, numarray, visit);
			visit[i] = false;

		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] numarray = new int[M];
		boolean[] visit = new boolean[N];
		dfs(0, N, M, numarray, visit);
	}

}