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

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

 

풀이

문제 예시를 보면,

사이클1 : 1 -> 3 -> 1
사이클2 : 5 -> 5

인 경우가 정답에 해당 된다.

 

즉, 만들어지는 사이클에 속하는 숫자들을 출력하면 된다.

 

예시에서도 보면 알겠지만, 사이클은 재귀 방식으로 탐색할 수 있다.

사이클이 만들어지는지 탐색할 때 중간에 거치는 숫자들을 임시 리스트에 담았다가, 사이클이 만들어지면 임시 리스트에 담긴 값을 정답 리스트에 담는다.

어떤 한 숫자가 사이클에 속하게 되면 다른 사이클에는 속할 일이 없으므로, 사이클을 탐색할 때 정답 리스트에 없는 숫자로만 시작하면 된다.

 

재귀탐색 시 중단 조건은, 즉, 사이클을 이루는 조건은 탐색 중간값이 재귀탐색 시작점 값이 될 때이다.

 

main()

//사이클 탐색 시 방문 여부
static boolean[] isVisited;
//두 번째 줄 각 칸에 해당하는 숫자 배열
static int[] board;
//최종 사이클을 이루는 숫자 저장하는 리스트
static ArrayList<Integer> answerList = new ArrayList<>();
//사이클 재귀 탐색 시 중간에 거치는 숫자 임시로 저장하는 리스트
static ArrayList<Integer> tempList = new ArrayList<>();


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

    int N = Integer.parseInt(br.readLine());
    board = new int[N+1];
    isVisited = new boolean[N+1];

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

    for (int i = 1; i <= N; i++) {
        //이미 사이클을 이루는 숫자는 다른 사이클에 속할 수 없으므로
        //사이클을 이루지 못한 숫자만 재귀 탐색의 시작점으로!
        if (!answerList.contains(i)) {
            //시작지점 방문 true
            isVisited[i] = true;
            //시작지점 임시 리스트 저장
            tempList.add(i);
            //사이클 재귀 탐색
            dfs(i, i);
            //시작지점 방문 false
            isVisited[i] = false;
            //시작지점 임시 리스트에서 제거
            tempList.remove((Integer)i);
        }
    }//for end

    StringBuilder sb = new StringBuilder();
    int size = answerList.size();

    sb.append(size).append("\n");

    answerList.stream()
            .sorted()
            .forEach(num -> sb.append(num).append("\n"));

    System.out.println(sb);
}

 

 

dfs()

public static void dfs(int now, int start) {
    //중단조건
    //다음 탐색값이 탐색 시작점과 같으면 사이클을 이룸
    //임시 리스트에 저장된 값을 정답 리스트에 저장
    if (board[now]==start) {
        answerList.addAll(tempList);
        return;
    }

    //다음 탐색값이 현재 탐색 동안 방문하지 않았고, 이미 사이클을 이루지 않았으면 방문!
    if (!isVisited[board[now]] && !answerList.contains(board[now])) {
        isVisited[board[now]] = true;
        tempList.add(board[now]);
        dfs(board[now], start);
        isVisited[board[now]] = false;
        tempList.remove((Integer)board[now]);
    }
}