백준 16936 자바 - 나3곱2 (BOJ 16936 JAVA)

문제 : boj16936

 

 

  난이도 기여 멘트들을 보니 많은 분들이 ad hoc으로 보고 수학적으로 푼 것 같다. 3의 차수라는 내용이 많이 나오던데 솔직히 뭔지 잘 모르겠다 ㅋㅋ. 내 경우엔 수학적으로 잘 모르겠으니 그냥 무식하게 풀었다. 

 

  각 수를 하나의 정점으로 치고, 방향 그래프를 만든다. 만약 두 수 X, Y가 있고 X*2 == Y 혹은 X/3 == Y 라면 X->Y 처럼 X에서 Y로 가는 간선을 만든다. 예를들어 '예제 입력 1'에 대한 방향 그래프는 다음과 같다.

 

  이렇게 모든 쌍에 대해 간선을 만들고 (모든 쌍이라고 해봐야 100x100개 뿐임), 모든 정점에서 출발해서 DFS를 돌린다. 어떠한 지점에서 DFS를 통해 모든 정점에 갈 수 있다면 해당 루트를 출력해주면 된다.

 

  여기서 좀 더 효율적으로 처리하려면, 간선이 연결되는 차수를 세보자. 예를들어 X->Y 처럼 된다면, Y의 차수를 1 증가시켜준다. 그리고 차수가 낮은 순서대로 DFS를 진행하면 된다. 사실 항상 정답이 존재하는 경우만 주어지므로, 차수가 0인 위치에서 출발하는 것은 항상 정답이 된다. 하지만 여러 정답이 있는 경우가 충분히 발생할 수 있으므로 모든 차수를 순회하도록 코드는 짜둬야 한다.

 

 

 

코드 : github

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

public class Main {
    private static final long MAX_DIV_2 = 1000000000000000000l/2;
    private long[] answer, arr;
    ArrayList<Integer>[] edge;
    boolean[] v;
    int n;

    private boolean dfs(int s, int cnt) {
        answer[cnt] = arr[s];
        if (cnt == n-1) {
            return true;
        }

        for (int next : edge[s]) {
            if (v[next]) continue;
            v[next] = true;

            if (dfs(next, cnt+1)) return true;
            v[next] = false;
        }
        return false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        answer = new long[n];
        arr = new long[n];
        v = new boolean[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Long.parseLong(st.nextToken());

        edge = new ArrayList[n];
        for (int i = 0; i < n; i++) edge[i] = new ArrayList<>();
        int[] cnt = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (arr[i]%3==0 && arr[i]/3==arr[j] || arr[i]<MAX_DIV_2 && arr[i]*2==arr[j]) {
                    edge[i].add(j);
                    cnt[j]++;
                }
            }
        }

        for (int targetCnt = 0; ; targetCnt++) {
            for (int i = 0; i < n; i++) {
                if (cnt[i] == targetCnt)
                    if (dfs(i, 0)) {
                        StringBuilder sb = new StringBuilder();
                        for (long tmp : answer)
                            sb.append(tmp).append(' ');
                        System.out.println(sb);
                        return;
                    }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}