[연습문제] 혼자 놀기의 달인 - JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

---

음 이 문제는 DFS로 해결 가능한 문제였던 것 같다

1번 카드(0번 인덱스)부터 차례대로 방문하면서 해당 인덱스의 카드값이 다음 인덱스가 되도록 한다

그리고 방문한 카드의 인덱스는 visit 배열을 통해 방문 처리를 하고, 이미 방문한 경우 방문한 카드 개수를 배열에 저장한다

그 후 내림차순 정렬해서 최댓값 2개의 곱을 반환하면 된다

 

내가 헷갈렸던 부분은 DFS를 적용해서 몇 개의 노드를 방문하는지 체크하는 depth 부분이 약간 헷갈렸다

이 부분은 구현할 때마다 헷갈리는 것 같다ㅠㅠ

그래서 depth를 전역 변수로 선언하고 dfs 특성상 재귀호출을 하니까, 재귀호출 시마다 depth를 1씩 증가시키는 방식으로 구했다

 

설명이 모호하긴 한디 코드 보면 이해가 갈것이다~

 

 

 

 

 

자바 코드)

import java.util.*;

class Solution {
    static boolean[] visit;
    static int depth;

    public int solution(int[] cards) {
        int answer = 1;
        int len = cards.length;
        visit = new boolean[len+1];
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<len;i++) {
            if(!visit[i+1]) {
                depth = 1;
                visit[i+1] = true;
                open(cards[i], cards);
                list.add(depth);
            }
        }
        if(list.size()<2) {
            return 0;
        }
        Collections.sort(list, Collections.reverseOrder());
        answer = list.get(0) * list.get(1);
        return answer;
    }

    private static void open(int x, int[] cards) {
        if(!visit[x]) {
            visit[x] = true;
            depth += 1;
            open(cards[x-1], cards);
        }
    }
}