[백준] 15663: N과 M (9)(Java)

Yoon Uk·2022년 7월 2일

DFS Java 백준 백트래킹 알고리즘

알고리즘 - 백준

목록 보기

14/130

문제

BOJ 15663: N과 M (9) https://www.acmicpc.net/problem/15663

풀이

처음에 했던 잘못 된 풀이

잘못된 풀이 클릭

잘못된 풀이 방법

이런 방식으로 ArrayList를 두 개 만들어 중복인 값은 list2에 넣어 따로 처리를 해보려고 했다.
이렇게 하면 입력값이 모두 같을 때 출력이 여러번 된다.
- 방문처리를 중복되는 수가 아닐 때만 true로 해 줘서 그런 것 같다.

잘못된 코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M;
	static int[] arr, printArr;
	static ArrayList<Integer> list1;
	static ArrayList<Integer> list2;
	static boolean[] isVisited;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		list1 = new ArrayList<>();
		list2 = new ArrayList<>();
		
		arr = new int[N];
		printArr = new int[M];
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		for(int i=0; i<arr.length-1; i++) {
			if(arr[i] == arr[i+1]) { // 중복되는 수
				list1.add(arr[i]);
				list2.add(arr[i+1]);
			} else { // 중복되는 수가 아니면
				list1.add(arr[i]);
				list2.add(0);
			}
		}
		isVisited = new boolean[list1.size()];
		
		
		dfs(0);
		System.out.println(sb);
	}
	
	static void dfs(int depth) {
		if(depth == M) {
			for(int i=0; i<M; i++) {
				sb.append(printArr[i] + " ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i=0; i<list1.size(); i++) {
			if(!isVisited[i]) {
				
				if(list2.get(i) == 0) { // 중복되는 수가 아니면
					isVisited[i] = true;
					printArr[depth] = list1.get(i);
				} else if(list2.get(i) > 0) { // 중복되는 수
					printArr[depth] = list2.get(i);
				}						
				
				dfs(depth + 1);
				
				isVisited[i] = false;
			}	
		}
	}
}

정답 풀이

입력 받은 배열을 오름차순으로 정렬한다.
현재 값(now)과 바로 이전의 값(past) 을 기록해 중복 여부를 확인한다.

코드

import java.util.*;
import java.io.*;

public class Main {

	static int N, M;
    static int[] arr, printArr;
    static boolean[] isvisited;
    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[N];
	     printArr = new int[N];
	     isvisited = new boolean[N];
	     st = new StringTokenizer(br.readLine());
	     for (int i = 0; i < N ; i++) {
	         arr[i] = Integer.parseInt(st.nextToken());
	     }

	     Arrays.sort(arr);
	     
	     dfs(0);
	     System.out.println(sb);
	}
	
	public static void dfs(int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(printArr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        int past = -1;
        for (int i = 0; i < arr.length; i++) {
            int now = arr[i];
            if (isvisited[i] || past == now) { // 방문 했거나 바로 이전 값과 중복 이면 
                continue;
            } else { //중복 x
                past = now; // 현재 값을 past 값에 넣음
                isvisited[i] = true;
                printArr[depth] = arr[i];
                dfs(depth + 1);
                isvisited[i] = false;
            }
        }
    }

}