[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS - 기출문제

DFS, BFS 기출문제 풀이

순열 구하기

설명 : 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
입력 설명 : 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다. 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.
출력 : 첫 번째 줄에 결과를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
풀이 답안

package org.example;

import java.util.*;

public class Main {

    static int total, sel;
    static int[] arr,chk,result;
    public void DFS(int L){

        if(L==sel) {
            for (int i : result) {
                System.out.print(i+" ");
            }
            System.out.println();
        } else {
            for(int i=0; i<total; i++){
                if(chk[i]==0){
                    chk[i] = 1;
                    result[L] = arr[i];
                    DFS(L+1);
                    chk[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        total = scan.nextInt();
        sel = scan.nextInt();
        arr = new int[total];
        chk = new int[total];
        result = new int[sel];
        for(int i=0; i<total; i++){
            arr[i] = scan.nextInt();
        }

        t.DFS(0);
    }
}

정리
- 처음 작성했을때는 순서 상관없이 경우의 수만 뽑으면 되는줄알고 기초적인 쉬운 문제라고 생각했으나 3-6 6-3 등의 반대도 가능한 문제였음
- 인자로 v+1를 넘기던 일전의 풀이방식과 달라져 고민을했고, 이때 반복문을 사용하면 동일 답안이 반복 출력되는 문제가 발생
- 매개변수로 현재의 수를 주는게 아니라 레벨(결과값의 몇번째 인덱스인지)를 넣어줘서 풀이해야했음
- 이때 체크변수를 만들어 체크된 수==자신은 반영되지 않도록 하고 다른 수만 다음 항목으로 적용될수 있도록 함
- 풀이방식이 달라진것이라 잊을만할때 다시 한번 풀어보면 좋을것같음

IM

DFS, BFS 기출문제 풀이

순열 구하기