[백준] 10819번

사이트

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

10819번: 차이를 최대로

 

문제 

 

분석

문제는 뭔가 쉬워보여서 바로 도전했지만 그렇지가 않았다. 

초반에 큰수 작은수로 정렬해서 어떻게든 해볼려 했는데 뭔가 이상했다... 

그래서 문제 유형을 봤더니 백트래킹... 즉 재귀함수를 사용해야 했다. 

재귀함수가 너무 어렵다... 

 

필자가 생각한 알고리즘은 재귀함수를 구현해서 만약 입력이 6개면 트리구조 처럼 

1 2 3 4 5 6 /// 1 2 3 4 6 5 // 1 2 3 5 4 6 이렇게 끝의 있는 숫자를 바꾸면서 구현하고 싶었다. 

하지만 너무 어렵웠고 아직 미숙해서 다른사람들이 한거를 참고해서 만들었다...  

그래도 내가 생각한 알고리즘이 맞았기에 만족은 한다!! 

서론이 너무길었다. 본론 시작 !! 

 

static int n;
static int [] arr;

static int [] result;

static int max=Integer.MIN_VALUE;

static boolean[] visit;

다음과 같이 스태틱 필드 변수를 선언했다. 다른건 다 그렇다 쳐도 visit boolean 배열을 추가한 이유는 숫자를 바꿀때 기록하기 위함이다. 

public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    n=Integer.parseInt(br.readLine());
    arr=new int[n];
    st=new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++){
        arr[i]=Integer.parseInt(st.nextToken());
    }
    visit=new boolean[n];
    result=new int[n];
    dfs(0);
    System.out.println(max);
}

입력이 시작되고 dfs(0)을 호출함으로써 본격적인 코드가 실행된다! 

 

public static void dfs(int depth){
    if(n==depth){
        int sum=0;
        for(int i=0; i<n-1; i++){
            sum+=Math.abs(result[i]-result[i+1]);
        }
        max=Math.max(sum,max);
        return;
    }

    for (int i=0; i<n; i++){
        if(!visit[i]){
            visit[i]=true;
            result[depth]=arr[i];
            dfs(depth+1);
            visit[i]=false;
        }
    }

}

여기가 dfs 함수 구조이다 차근 차근 보자. 

일단 들어온 값이 0이므로 n의 크기는 6으로 가정했을때 크기가 맞지 않으므로 아래 for문으로 이동한다. 

즉 저 if문은 배열의 요소들이 다 정렬되었을 때 실행이 된다. 

 

for (int i=0; i<n; i++){
    if(!visit[i]){
        visit[i]=true;
        result[depth]=arr[i];
        dfs(depth+1);
        visit[i]=false;
    }
}

중요한 로직은 바로 이거다! 집중해서 읽자 

for문으로 들어오면 i=0일때 visit[0]은 일단 false 이므로 들어온다 .

 

dfs(0)

그러고나서 true로 변환시켜주고 arr[0] 즉 우리가 입력한 배열 요소의 값을 result[depth]에 저장한다. 즉 dfs(0) 했을때 저 0이다.

그러면 result 배열의 첫번째 요소는 저장이 된것이다. 그다음 dfs(1)을 호출한다 여기서 중요한점은 아직 dfs(0)은 끝나지 않았다는 것이다! 

 

dfs(1) 쭉

depth가 1이면 for문으로 들어온다. 이때 visit[0]은 true라서 visit[1]이 들어온다. 그럼 동일하게 result에 또 저장이 된다. 

이렇게 쭉 저장되다가 depth가 5가되면 result 배열은 완성이 되었고 dfs(6)을 호출한다. 

if(n==depth){
    int sum=0;
    for(int i=0; i<n-1; i++){
        sum+=Math.abs(result[i]-result[i+1]);
    }
    max=Math.max(sum,max);
    return;
}

그럼 위에 있는 if문에 걸리면서 Math.max를 통해 배열에 합한 값들이 max에 저장이 된다. 그리고 return 하게 된다. 

 

변화

그럼 dfs(6) 함수는 끝나게 되고 다시 dfs(5) 함수로 오게 된다.

for (int i=0; i<n; i++){
    if(!visit[i]){
        visit[i]=true;
        result[depth]=arr[i];
        dfs(depth+1);
        visit[i]=false;
    }
}

그럼 dfs(5) 함수는 위에 있는 visit[i]=false를 실행하게 된다. 이떄 dfs(5) 함수일때 i는 5이므로 visit[5]는 true가 아닌 false가 된다.

 

그 다음 어떻게 될까??? for 문이 끝났으므로 dfs(5) 도 끝났다! 그럼 dfs(4)가 호출이된다. 

위와 동일하게 dfs(4)도 visit[4]가 false로 바뀌고 다음 for문 i=5가 저장이 된다. 

이전: result[4]=arr[4]

바뀐후: result[4]=arr[5] 이렇게 말이다. 즉 필자가 앞에서 말했던것처럼 순서가 바뀐것이다! 

 

그럼 다시 dfs(5)로 호출이 되고 새롭게 호출되므로 for문을 처음 부터 돌려 

이전: result[5]=arr[5]

바뀐후: result[5]=arr[4] 이렇게 저장이 된다.

 

그러고 나서 또 dfs(6)을 호출하고 무한 반복이 되다가 depth가 0일떄 즉 dfs(0) 일때 for문이 완료됐으면 종료되는 것이다! 

종료되면서 최대값을 반환하는 것이다!! 

 

전체 코드

package bra;

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

public class Bra10819 {

    static int n;
    static int [] arr;

    static int [] result;

    static int max=Integer.MIN_VALUE;

    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n=Integer.parseInt(br.readLine());
        arr=new int[n];
        st=new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        visit=new boolean[n];
        result=new int[n];
        dfs(0);
        System.out.println(max);
    }
    public static void dfs(int depth){
        if(n==depth){
            int sum=0;
            for(int i=0; i<n-1; i++){
                sum+=Math.abs(result[i]-result[i+1]);
            }
            max=Math.max(sum,max);
            return;
        }

        for (int i=0; i<n; i++){
            if(!visit[i]){
                visit[i]=true;
                result[depth]=arr[i];
                dfs(depth+1);
                visit[i]=false;
            }
        }

    }
}

 

결과

 

느낀점

와 진짜 재귀함수 너무 어렵다... 이 정답률이 65프로인데 사람들은 어떻게 맞힌 걸까??? 

필자도 알고리즘은 알고 있으나 직접 코드로 못써... 참조했는데... 

열심히 노력하자 풀어보니깐 또 어렵진 않았다.. 

그래프가 최곤데 ㅜㅜ