[백준](Java) 2668 - 숫자고르기

문제 링크

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

문제 풀이

세로 두줄 가로 N칸을 구현하기 위해서 Map을 사용했다. 위의 줄은 1,2,3 ... 순서대로 중복없이 존재하지만, 아랫줄은 입력받은 숫자들이 중복상관없이 존재하므로 위의줄을 key, 아래줄을 value 값으로 해서 Map을 만들었다.
up, down list들은 각각 윗줄에서 싸이클을 형성할떄의 값, down은 아랫줄에서 싸이클을 형성할때의 값들을 모아두려고 만들었고 싸이클이 끊기거나 완성되었을때 list를 비교하여 일치한다면 완성된 싸이클을 저장하는 res에 저장한다.

        map = new HashMap<>();
        chk = new boolean[n + 1];
        up = new ArrayList<>();
        down = new ArrayList<>();
        res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            map.put(i + 1, num);
        }

dfs를 가기전에 해당 숫자를 방문해서 싸이클에 방문했는지 체크를 하고, 방문한적이 없으면 dfs로 진행한다.
dfs에서 넘어올때의 값이 이미 방문한적이 없다면
윗줄의 값은 up에, 아랫줄의 값은 down에 넣고 방문 체크를 한다음에 dfs를 통해서 다음 값을 찾는다.

else {
            up.add(idx);
            chk[idx] = true;
            down.add(map.get(idx));
            dfs(map.get(idx));
        }

해당 과정을 반복하다가 이미 방문한 곳에 도착했을 경우에 up, down을 비교하여 일치한다면 문제의 조건에 부합하는것이므로 res에다가 이번 싸이클에서 구한 값들을 넣어주고

if (down.containsAll(up)) {
                for (int i = 0; i < up.size(); i++) {
                    res.add(up.get(i));
                }
            } 

만약에 일치하지 않게 된다면 방문 체크는 다시 되돌려야 한다.

else {
                for (int i = 0; i < down.size(); i++) {
                    if(!res.contains(down.get(i))){
                        chk[down.get(i)] = false;
                    }
                    if(!res.contains(up.get(i))) {
                        chk[up.get(i)] = false;
                    }
                }

한번의 과정이 끝나면 up, down을 비워준다.

            up.clear();
            down.clear();

위와 같은 방법으로 윗줄의 모든 값들에 대해서 한번씩 dfs를 돈후에
res값을 정렬하고 값을 출력한다.

        System.out.println(res.size());
        Collections.sort(res);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }

코드

import java.util.*;

public class Main {

    static int n;
    static Map<Integer, Integer> map = new HashMap<>();
    static boolean[] chk;
    static List<Integer> up;
    static List<Integer> down;
    static List<Integer> res;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        map = new HashMap<>();
        chk = new boolean[n + 1];
        up = new ArrayList<>();
        down = new ArrayList<>();
        res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            map.put(i + 1, num);
        }


        for (int i = 1; i <= n; i++) {
            if (chk[i] || chk[map.get(i)]) {
                continue;
            }
            dfs(i);
            up.clear();
            down.clear();
        }

        System.out.println(res.size());
        Collections.sort(res);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }

    public static void dfs(int idx) {

        if (chk[idx]) {
            if (down.containsAll(up)) {
                for (int i = 0; i < up.size(); i++) {
                    res.add(up.get(i));
                }
            } else {
                for (int i = 0; i < down.size(); i++) {
                    if(!res.contains(down.get(i))){
                        chk[down.get(i)] = false;
                    }
                    if(!res.contains(up.get(i))) {
                        chk[up.get(i)] = false;
                    }
                }
            }

            return;
        } else {
            up.add(idx);
            chk[idx] = true;
            down.add(map.get(idx));
            dfs(map.get(idx));
        }


    }
}