[백준 JAVA] 회귀한 프로그래머의 순열 응용 문제 다시 풀기

• 차이를 최대로
• 외판원 순회 2
• 로또

다음 문제들을 풀어보려고 한다.

 

느낀점 1: 순열을 풀때는 10이하면 dfs, 10 이상이면 반드시 NextPermutation 을 사용해야하지만 현실적으로 그런문제는 많이 없는것 같다. 그래도 NextPermutation을 안보고 짤 수 있게 되었다.

 

느낀점 2: 오랜만에 백트래킹을 접했더니 감회가 새로웠다. 파라미터로 어떤거를 넘겨줄껀지 고민했던 시간들이 스쳐지나간다. 그리고 문제에서 처음봤을때 생각하지 못했던 것들을 다른 사람들의 풀이를 보고 깨달은 부분도 있어서 문제를 쉽게 풀었다 해도 다른사람의 풀이도 꼭 한번쯤 보기

 

차이를 최대로

N이 8까지고 완전탐색으로 모든 순열을 구해서 식의 값을 최대로 구하면 되는 문제이다.

 

만약 N이 너무 크다면 dfs 말고 NextPermutation으로 풀어야되고 

 

아니면 사실 식의 최대값이므로 탐욕적인 방법으로 풀 수도 있을꺼같다는 생각이 들었다.

 

하지만 가장 쉬운방법으로 다시 풀어보자.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N, ans = Integer.MIN_VALUE;
    public static int[] num, arr, visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        num = new int[N];
        arr = new int[N];
        visited = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N;i ++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);

        System.out.println(ans);
    }

    public static void dfs(int depth){
        if(depth == N){
            int temp = 0;
            for(int i = 1; i < N; i++){
                temp += Math.abs(arr[i - 1] - arr[i]);
            }
            ans = Math.max(temp, ans);

            return;
        }

        for(int i = 0; i < N; i++){
            if(visited[i] == 1) continue;
            arr[depth] = num[i];
            visited[i] = 1;
            dfs(depth + 1);
            visited[i] = 0;
        }
    }
}

 

 

외판원 순회 2

W[i][j] = 0 인경우는 가지못하는길이므로 하나라도 존재하면 정답에서 제외해야 하는데 이 부분을 하지못해서 좀 해맸다. 

 

dfs 로 풀었을때는 그냥 함수를 return 해주면 되서 편했는데 NextPermutation 은 이 계산하는 과정을 do - while 문으로 하기 때문에 break 나 continue; 로 해결할 수 없어서 좀 힘들었다.

 

GPT 한테 물어본결과 예전에 자주 사용하던 valid 를 이용하는 방식을 알려줘서 그렇게 풀었는데 코드가 썩 맘에 들진 않는다.

 

또한 순회이기 때문에 시작지점을 고정해줘도 된다. 1 - 2 - 3 이나 2 - 3 - 1 이나 3 - 1 - 2 이나 같기 때문

 

다 풀고 블로그를 봤을때 백트레킹으로 푼사람이 있길래 그 방법으로도 풀어보았다.

 

 

같은 dfs 로 풀었을때 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N, ans = Integer.MAX_VALUE;
    public static int[] arr, visited;
    public static int[][] W;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        visited = new int[N];
        W = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0);

        System.out.println(ans);
    }

    public static void dfs(int depth){
        if(depth == N){
            int cnt = 0;
            int cost;
            for(int i = 1; i < N; i++){
                cost = W[arr[i - 1]][arr[i]];
                if(cost == 0) return;
                cnt += cost;
            }
            cost = W[arr[N-1]][arr[0]];
            if(cost == 0) return;
            cnt += cost;

            ans = Math.min(cnt, ans);

            return;
        }

        for(int i = 0; i < N; i++){
            if(visited[i] == 1) continue;
            arr[depth] = i;
            visited[i] = 1;
            dfs(depth + 1);
            visited[i] = 0;
        }
    }
}

 

NextPermutation 으로 풀었을때

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N, ans = Integer.MAX_VALUE;
    public static int[] arr;
    public static int[][] W;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        W = new int[N][N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 0; i < N; i++) {
           arr[i] = i;
        }

        do {
            int cnt = 0;
            int cost = 0;
            boolean valid = true;
            for(int i = 1; i < N; i++){
                cost = W[arr[i-1]][arr[i]];
                if(cost == 0) {
                    valid = false;
                    break;
                }
                cnt += cost;
            }

            if(valid) {
                cost = W[arr[N-1]][arr[0]];
                if(cost == 0) {
                    valid = false;
                } else {
                    cnt += cost;
                }
            }

            if(valid) {
                ans = Math.min(cnt, ans);
            }
        } while(np(arr));

        System.out.println(ans);
    }
    public static boolean np (int[] p){
        // 1. 피봇 찾기
        int i = N - 1;
        while(i > 0 && p[i - 1] >= p[i]) --i;

        if(i == 0){
            return false;
        }

        // 2. 스왑지점 찾기
        int j = N - 1;
        while(p[i - 1] >= p[j]) --j;
        swap(p, i - 1, j);

        // 3. 오름차순 정렬하기
        int k = N - 1;
        while(i < k) {
            swap(p, i++, k--);
        }

        return true;
    }
    public static void swap(int[] p, int i, int j){
        int temp = p[i];
        p[i] = p[j];
        p[j] = temp;
    }
}

 

dfs + 백트레킹

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N, ans = Integer.MAX_VALUE;
    public static int[] visited;
    public static int[][] W;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        visited = new int[N];
        W = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visited[0] = 1;
        dfs(0, 0, 1);

        System.out.println(ans);
    }

    public static void dfs(int now, int cost, int depth){
        if(depth == N && W[now][0] != 0){
            ans = Math.min(cost + W[now][0], ans);
            return;
        }

        for(int i = 1; i < N; i++){
            if(W[now][i] == 0 || visited[i] == 1) continue;
            visited[i] = 1;
            dfs(i, cost + W[now][i], depth + 1);
            visited[i] = 0;
        }
    }
}

 

 

 

맨위가 dfs+백트레킹

dfs

NextPermutation으로 풀었을때 시간이다.

 

이정도범위에서는 이렇게 결과가 나왔지만 수가 더 커진다면 유의미 할것같다.

로또

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] num, arr;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        while(true) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if(N == 0) break;

            num = new int[N];
            arr = new int[6];

            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }

            dfs(0,0);

            sb.append("\n");
        }

        System.out.println(sb);
    }

    public static void dfs(int at, int depth){
        if(depth == 6){
            for(int a : arr){
                sb.append(a).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i = at; i < N; i++){
            arr[depth] = num[i];
            dfs(i + 1, depth + 1);
        }
    }
}

 

이문제는 순열보다는 조합문제인것같다.