[DFS] 혼자 놀기의 달인

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

프로그래머스

 

💡문제 분석 요약

상자  1번  2번  3번  4번  5번  6번  7번  8번
숫자   8      6      3     7      2     5      1      4

 

만약 1번상자-숫자8을 뽑을경우 뽑은 숫자인 8번이 적힌 상자에서 카드를 뽑는다

이미 연 상자 일 경우, 탐색을 종료한다.

 

1번상자(8) -> 8번상자(4) -> 4번상자(7) -> 7번상자(1) -> 1번상자(8) (X): 1번 상자는 이미 연 상자이므로 7번상자 까지가 첫번째 그룹이다.

 

💡알고리즘 설계

1. 몇번째 상자를 먼저 뽑는가에 따라, 그룹에 들어갈 상자의 개수도 달라지고 따라서 얻는 점수도 달라진다.

2.  DFS : 연결된 상자(노드)를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들을 없을 때(이미 연 상자를 만났을때),

                종료하고 다른 상자(노드)를 뽑은 후 다시 DFS로  연결된 노드를 따라서 탐색을 한다.

 

💡시간복잡도

제한사항

2<= cards의 길이 <=100

 

내부 DFS 호출(for 반복문)이 O(n)번 발생하고, 그 각각의 호출에서 최대 O(n)의 작업을 수행하므로, 이 부분의 시간 복잡도는 O(n^2)입니다.

따라서 O(100^2) 최대 10000번의 연산이 진행된다.

최악의 경우인, 10000번의 연산의 경우 테스트에 통과 할 정도니 문제는 없을 거 같다.

 

정렬(Collections.sort)은 O(m log m) 시간이 소요된다. 여기서 m은 linkSum 리스트의 길이.

💡코드

import java.util.*;
class Solution {
    boolean[] visited;
    int depth;
    public int solution(int[] cards) {
        int answer = 0;
        int len = cards.length;
        List<Integer> linkSum = new ArrayList<>();  // 그룹에 속한 상자들의 합
        visited = new boolean[len+1];				// 상자의 번호가 1번부터 시작이므로 visited의 인덱스도 여기에 맞춘다
        
        for(int i=0;i<len;i++){
            if(!visited[i+1]){
            depth=1;				// 첫번째 뽑은 상자이므로 depth=1로 셋팅
            visited[i+1] = true;	// 
            
            dfs(cards[i], cards);
            linkSum.add(depth);
            }
        }
           if(linkSum.size()<2) {   // 상자 그룹이 1개밖에 없으면 점수는 0점.
            return 0;
        }
        
        Collections.sort(linkSum,Collections.reverseOrder());
        answer = linkSum.get(0)*linkSum.get(1);
        return answer;
    }
    private void dfs(int x, int[] cards){
        if(!visited[x]){
            visited[x] = true;
            depth += 1;
            dfs(cards[x-1], cards);		//여기서 x는 인덱스가 아닌 '~번째'이므로 -1 하여 인덱스로 바꿔준다
        }
    }
}

 

💡 느낀점 or 기억할정보

재귀의 성격을 가진 DFS의 경우 for문과 함께 쓸 경우, 시간복잡도를 따져보는게 중요하다.

평소에 시간복잡도를 따지는 연습을 많이 하자.