[백준] 2668번 : 숫자고르기 Gold5(골드5) - JAVA[자바]

[Gold V] 숫자고르기 - 2668

문제 링크

성능 요약

메모리: 11584 KB, 시간: 80 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2023년 12월 12일 09:34:56

문제 설명

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

풀이 방법

1. 싸이클이 존재하는지 확인한다.

2. 재귀 방식이 아닌 스택으로 dfs를 구현하면서 List에 방문경로를 저장해준다.

3. 현재 위치가 goal과 같다면 answer에 현재 방문 경로를 전부 삽입함

4. List를 정렬 후 사이즈와 원소값들을 출력해준다.

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

public class Main {
    static int[] nums;
    static List<Integer> answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        nums = new int[n+1];
        answer = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            nums[i] = Integer.parseInt(br.readLine());
        }
        // 싸이클이 없는 원소값이라면 dfs호출
        for(int i = 1; i <= n ;i++){
            if(!answer.contains(i)){
                dfs(i,i);
            }
        }
        // 정렬 후 리스트의 사이즈와 원소값 호출
        Collections.sort(answer);
        System.out.println(answer.size());
        for(int num : answer){
            System.out.println(num);
        }
    }
    private static void dfs(int pos, int goal) {
        // dfs를 위한 stack
        Stack<Integer> stack = new Stack<>();
        // 방문한 위치를 저장하는 list
        ArrayList<Integer> list = new ArrayList<>();
        list.add(pos);
        stack.push(pos);
        while(!stack.isEmpty()){
            // 현재 방문 한 위치값 
            int n = stack.pop();
            // 현재 위치가 goal과 같다면 지금까지 방문한 곳을 answer에 저장
            if(nums[n] == goal){
                for(int num : list){
                    answer.add(num);
                }
                return;
            }
            // answer에 있는 것 == 싸이클이 있는 것 -> 호출해도 의미 없으므로 스킵
            // List에 있는 것 == 이미 방문한 것 -> 방문하지 않은 곳에소만 호출
            if(!answer.contains(nums[n])&&!list.contains(nums[n])){
                list.add(nums[n]);
                stack.push(nums[n]);
            }
        }

    }
}