[백준/java] 2668. 숫자고르기

문제보기

문제

표 첫째줄엔 1~N까지 순서대로, 둘째줄엔 입력대로의 집합이 있을 때,
뽑힌 첫째줄 정수들과 둘째줄 정수들의 집합이 최대로 많이 일치하는 경우의 수를 구하라.

예를 들어, 이 경우에는 1,3,5를 뽑는 것이 답이다.
첫째줄 1,3,5를 뽑으면 둘째 줄 3,1,5로 두 집합은 일치하고, 집합의 크기는 3이다.

• 입력 : 정수 N(<= 10^2), 표 둘째줄 정수들
• 출력 : 첫째줄에 뽑힌 정수들의 최대 갯수, 뽑힌 정수들 오름차순

문제 풀이

static int[] graph; // 첫째줄 숫자 i, 둘째줄 숫자 graph[i] 매핑

탐색하기 편하기위해 배열을 이용해 첫째줄 숫자를 i, 둘째줄 숫자를 graph[i]로 매핑하였다.

for(int i = 1; i <= N; i++){
            if(!visited[i]) {
                boolean[] pathVisited = new boolean[N + 1];
                dfs(i,i,pathVisited);
            }
        }
        
private static void dfs(int start, int current,boolean[] pathVisited) {
        if(pathVisited[current]){
           if(current == start) { // 집합 조건이 맞을 시, 카운트 세기
                for(int i = 1; i <= N; i++){ // 카운트 세기 : visited 갱신
                    if(pathVisited[i] && !visited[i]) visited[i] = true;
                }
            }
            return;
        }

        pathVisited[current] = true;
        int next = graph[current];
        dfs(start,next,pathVisited);

    }

1. 첫째 줄의 숫자 start를 기준으로,
   둘째 줄에서 매핑된 숫자 next를 따라가며
   다시 start로 돌아오는 순환 사이클이 존재하는지 확인한다.
   ( graph[i] → graph[graph[i]] → ... -> i 형태의 사이클 )

2. 만약 사이클이 존재하면,
   이번 탐색 경로에서 방문한 pathVisited 배열을
   전체 방문 상태를 기록하는 visited 배열에 반영하여 갱신한다.

3. 이 과정을 모든 숫자에 대해 반복하여,
   최종적으로 사이클에 포함된 숫자들만 visited에 남기고 출력한다.

전체 코드

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

public class Main {
    static int N,ans = 0;
    static int[] graph; // 첫째줄 숫자 i, 둘째줄 숫자 graph[i] 매핑
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        graph = new int[N + 1];
        visited = new boolean[N + 1];

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

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

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i<=N;i++){
            if(visited[i]){
                ans++;
                sb.append(i).append("\n");
            }
        }
        System.out.println(ans);
        System.out.println(sb.toString());

    }

    private static void dfs(int start, int current,boolean[] pathVisited) {
        if(pathVisited[current]){
           if(current == start) { // 집합 조건이 맞을 시, 카운트 세기
                for(int i = 1; i <= N; i++){ // 카운트 세기 : visited 갱신
                    if(pathVisited[i] && !visited[i]) visited[i] = true;
                }
            }
            return;
        }

        pathVisited[current] = true;
        int next = graph[current];
        dfs(start,next,pathVisited);

    }
}

시간복잡도

O(N^2)

문제를 읽었을 때, dfs 유형이라는 생각이 빨리 들지 못해 헤맸다. 예시로 차근차근 일일히 풀이를 생각하다가 사이클 형태임을 알게 되고, dfs 인 것을 알게 되었다.