[백준 2668번] 숫자고르기 || [백준 9466번] 텀 프로젝트

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

 

 

수정

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

public class Graph2668 {

    static int N;

    static int[][] map;

    static boolean resultFlag;

    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[2][N];

        for (int init = 1; init <= N; init++) {
            map[0][init - 1] = init;
        }

        for (int i = 0; i < N; i++) {
            map[1][i] = Integer.parseInt(br.readLine());
        }


        resultFlag = false;

        for (int level = N; level > 0; level--) {
            permutation(level, new ArrayList<>(), 0);
            if (result != null) {
                System.out.println(level);
                for (Integer integer : result) {
                    System.out.println(integer);
                }
                break;
            }
        }

        if (result == null) {
            System.out.println(0);
        }
    }

    private static void permutation(int length, List<Integer> aggregate, int index) {

        if (aggregate.size() == length) {
            result = selectNum(aggregate);
            if (result != null) {
                resultFlag = true;
            }
            return;
        }

        if (!resultFlag) {
            for (int i = index; i < N; i++) {
                aggregate.add(i);
                permutation(length, aggregate, i + 1);
                aggregate.remove(aggregate.size() - 1);
                if (resultFlag) break;
            }
        }

    }

    private static List<Integer> selectNum(List<Integer> aggregate) {
        List<Integer> compareA = new ArrayList<>();
        List<Integer> compareB = new ArrayList<>();

        for (Integer index : aggregate) {
            compareA.add(map[0][index]);
            compareB.add(map[1][index]);
        }

        System.out.println(compareA);
        Collections.sort(compareA);
        Collections.sort(compareB);




        if (compareA.equals(compareB)) {
            return compareA;
        } else {
            return null;
        }
    }
}

 

 

수정 후

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Graph2668 {

    static int N;
    static int[] map;
    static boolean[] visited;

    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N + 1]; // 1-based index
        for (int i = 1; i <= N; i++) {
            map[i] = Integer.parseInt(br.readLine());
        }

        visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            dfs(i, i);
        }

        System.out.println(result.size());
        for (int num : result) {
            System.out.println(num);
        }
    }

    private static void dfs(int start, int current) {
        if (!visited[current]) {
            visited[current] = true;
            dfs(start, map[current]);
        } else {
            if (start == current) {
                result.add(start);
            }
        }
    }
}

 

 

완벽한 DFS 문제였다... 시간복잡도를 잘 계산해서 해보자 ㅜㅜ 

 

 

 

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

 

package graph;

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

public class Graph9466 {
    static int N;

    static boolean[] finished;

    static int[] map;

    static boolean[] visit;

    static int result;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            visit = new boolean[N + 1];
            finished = new boolean[N + 1];
            map = new int[N + 1];
            result = 0;

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


            for (int k = 1; k <= N; k++) {
                if (!visit[k]) {
                    teamMatching(k);
                }
            }


            System.out.println(N - result);

        }
    }

    private static void teamMatching(int cur) {
        visit[cur] = true;
        int next = map[cur];

        if (!visit[next]) {
            teamMatching(next);
        } else if (!finished[next]) {
            int i = next;

            while (i != cur) {
                result++;
                i = map[i];
            }
            result++; // 자기 자신
        }

        finished[cur] = true;

    }
}

 

사이클 문제 빡세다...! 숫자 문제랑 도시 분할 계획 문제랑 비슷한듯

핵심은 visit은 시험지를 이미 본 상태, finished는 시험 다 보고 집에 간 상태를 말한다. 

• visit은 “들어가기만 하면 바로 체크인 도장 찍기”
• finished는 “탐험 다 끝내고 나와야 도장 찍기”