[JAVA] 백준 15650 N과 M (1)_백트래킹

 

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

15650번: N과 M (2)

 

접근 : 

 

 -  최대 숫자 N 과 뽑는 갯수 M을 입력 받는다.

 

 - 1 부터 N 까지 M 개를 뽑는다.

 

 - 중복인 숫자는 뽑지 않는다.

 

 - dfs 에서 depth를 내려갈 때, 중복인 숫자인 경우 더 이상 내려가지 않고 올라간다.

  

 

코드 구현 : 

 

 - 이너 클래스 사용

import java.io.*;

public class Main {

	static class Dfs {
		private StringBuilder result;
		private int n;
		private int m;
		private int[] selected;
		private boolean[] visited;

		public Dfs(int n, int m) {
			this.n = n;
			this.m = m;
			this.result = new StringBuilder();
			selected = new int[m];
			visited = new boolean[n+1];
		}

		void doDfs(int depth) {
			if (depth == m) {
				for (int j = 0; j < m; j++) {
					result.append(selected[j]).append(" ");
				}
				result.append("\n");
				return;
			}

			for (int i = 1; i <= n; i++) {
				
				// 중복 숫자인 경우 더 이상 depth를 내려가지 않음 
				if (visited[i]) {
					continue;
				}
				
				selected[depth] = i;
				
				// 현재 숫자를 해당 배열에 인덱스로 사용하여 방문여부를 표기한다. 
				visited[i] = true;
				
				this.doDfs(depth + 1);
				// depth 가 감소함에 따라 해당 숫자를 비방문 상태로 초기화 한다. 
				visited[i] = false;
			}
		}

		String getResult() {
			return result.toString();
		}
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] inputs = br.readLine().split(" ");

		Dfs dfs = new Dfs(Integer.parseInt(inputs[0]), Integer.parseInt(inputs[1]));

		dfs.doDfs(0);

		System.out.println(dfs.getResult());
		br.close();
	}
}

 

 

 - 이너 클래스 사용 X

 

import java.io.*;
public class Main {
    private static int n;
    private static int m;
    private static int[] selected;
    private static boolean[] visited;
    private static StringBuilder sb;

    static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        selected = new int[m];
        visited = new boolean[n + 1];
        br.close();
    }

    static void recFunc(int k){
        if(k == m + 1) {
            for (int i : selected) {
                sb.append(i).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i = 1 ; i <= n ; i++){
            
            if(visited[i]) continue;
            
            selected[k-1] = i;
            
            visited[i] = true;

            recFunc(k+1);
            
            visited[i] = false;
        }
    }

	public static void main(String[] args) throws IOException {
        sb = new StringBuilder();
        input();
        recFunc(1);
        System.out.println(sb);
	}
}

 

 

*이너클래스 사용여부는 메모리량과 성능에서 유의미한 차이 없음