DFS - 요리사

서론

DFS는 가장 많이 쓰이는 알고리즘이다.

아마 대부분의 문제들은 DFS와 BFS 알고리즘으로 해결되기 때문에 꼭 알아야 한다.

DFS는 Stack 또는 재귀로 구현할 수 있는데 재귀로 구현하는 것이 직관적이고 가독성도 좋다.

DFS를 구현하기 전에 문제에서 원하는 조건을 꼭 알아야 한다. 중복이 되는지, 순서대로 하는 건지 등등..

조건에 따라서 방문했던 곳을 제 할 수 돼있고, 포함시킬 수 도있다. 그러므로 꼭 문제의 조건을 확인해야 한다.

만약 DFS가 구현하기 어렵다면 기본적인 틀을 외우고 문제를 풀어가며 이해한다.

 

구현 코드

1. 중복 가능 순열(1~2중에 3개 선택 중복가능)

 

public class PermutationNPIN {
    static int n;        //순열의 자리수
    static int[] numbers; //순열을 담을 배열
    static int testcase;


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        numbers = new int[n];
        permutation(0);
        System.out.println("순열이 생성된 수:"+testcase);
    }

/**
 * 순열을 만들어주는 함수
 * @param cnt = 배열 번호
 */
    private static void permutation(int cnt) {
        if(cnt == n)
        {
            testcase++;
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i = 1; i < n; i++) {
            numbers[cnt] = i;
            permutation(cnt+1);
        }

        // TODO Auto-generated method stub

    }

}

결과 값

2. 중복 불가능 순열 (1~3중에 3개 선택 중복 불가)

 

public class PermutationNPIR2 {
    static int n;        //순열의 자리수
    static int r;        //순열의 자리수
    static int[] numbers; //순열을 담을 배열
    static int testcase;
    static boolean[] check;


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        numbers = new int[r];
        check = new boolean[n];
        permutation(0);
        System.out.println("순열이 생성된 수:"+testcase);
    }

/**
 * 순열을 만들어주는 함수
 * @param cnt = 배열 번호
 */
    private static void permutation(int cnt) {
        if(cnt == r)
        {
            testcase++;
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!check[i])
            {
                check[i] = true;
                numbers[cnt] = i+1;
                permutation(cnt+1);
                check[i] = false;
            }
        }
    }

결과 값

 

문제에 적용

 

문제:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE

SW Expert Academy

 

알고리즘

1. N개의 재료 중에 N/2를 선택하는 것을 DFS로 구현한다.

-> 중복 안됨 순서 있음

 

2. 두 요리의 점수 차 중 가장 작은 차를 저장한다.

 

구현 코드

class Solution
{
    static int arr[][];
    static boolean check[];
    static int index[];
    static int index2[];
    static int num1;
    static int num2;
    static int N;
    static int min;
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        StringTokenizer s;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = Integer.parseInt(in.readLine());
            arr = new int[N][N];
            check = new boolean[N];
            index = new int[N>>1];
            index2 = new int[N>>1];

            for (int i = 0; i < N; i++) {
                s = new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s.nextToken());    
                }
            }
            min = 20001;
            DFS(0,-1);
            System.out.println("#"+test_case+" "+min);
        }
    }
    private static void DFS(int i,int a) 
    {
        if(i ==N>>1)
        {
            int cnt=0;
            for (int j = 0; j < N; j++) {
                if(!check[j])
                {
                    index2[cnt++] = j;
                }
            }

            for (int j = 0; j < N>>1; j++) {
                for (int j2 = j; j2 < N>>1; j2++) {
                    num1+=arr[index[j]][index[j2]] + arr[index[j2]][index[j]];
                }
            }
            for (int j = 0; j < N>>1; j++) {
                for (int j2 = j; j2 < N>>1; j2++) {
                    num2+=arr[index2[j]][index2[j2]] + arr[index2[j2]][index2[j]];
                }
            }
            if(Math.abs(num1-num2) < min)
                min = Math.abs(num1-num2);
            num1=0;
            num2=0;
            return;
        }
        else if(index[0] != 0)
            return;
        for (int j = 0; j < N; j++) 
        {
            if(!check[j] && a<j)
            {
                check[j] = true;
                index[i] = j;
                DFS(i+1,j);
                check[j] = false;
            }
        }
    }
}