[131130] 혼자 놀기의 달인

✔ 혼자 놀기의 달인

[프로그래머스 131130]

문제 분석하기

카드의 번호와 상자의 번호로 이어지는 경우를 모두 구해 갯수를 더하면 됨

 

예) [8, 6, 3, 7, 2, 5, 1, 4]

상자 1	상자 2	상자 3	상자 4	상자 5	상자 6	상자 7	상자 8	상자 그룹
8	6	3	7	2	5	1	4	상자 1 → 8 상자 8 → 4 상자 4 → 7 상자 7 → 1 상자 1 → 8 상자 그룹 1 = {1, 4, 7, 8}
8	6	3	7	2	5	1	4	상자 2 → 6 상자 6 → 5 상자 5 → 2 상자 2 → 6 상자 그룹 2 = {2, 5, 6}
8	6	3	7	2	5	1	4	상자 3 → 3 상자 3 → 3 상자 그룹 3 = {3}

손으로 풀어보기

1. 방문 배열을 선언하고 DFS 탐색을 진행하며 방문하도록 함
   • 이때 열었던 상자에 도달하면 지금까지 탐색한 상자의 갯수를 리스트에 저장
2. 리스트의 크기가 1이라면 상자 그룹이 하나만 존재하므로 0을 반환
3. 리스트의 크기가 2 이상이라면 리스트를 내림차순으로 정렬한 후, 가장 큰 두 값의 곱을 반환

슈도코드 작성하기

cards(상자 안에 들어있는 카드 번호)
list(상자 그룹에 속한 상자의 수들을 담은 리스트)
visited(방문 배열)
for(i -> 0부터 cards의 길이만큼) {
    if(!visited[i]라면) 
        dfs(cards, i, 0)
}
if(list의 크기가 1이라면)
    0 반환
list를 내림차순 정렬
list.get(0) * list.get(1) 반환

dfs {
    if(visited[i]라면) {
        list에 count 저장
        return;
    }
    visited[i]를 true로 갱신
    dfs(cards, cards[i] - 1, count + 1)
}

코드 구현하기

/**
 * 131130) 혼자_놀기의_달인
 */
public class L079_131130 {
    List<Integer> list;
    boolean[] visited;

    // cards(상자 안에 들어있는 카드 번호)
    public int solution(int[] cards) {
        // list(상자 그룹에 속한 상자의 수들을 담은 리스트)
        list = new ArrayList<>();
        // visited(방문 배열)
        visited = new boolean[cards.length];
        for (int i = 0; i < cards.length; i++) {
            // i에 방문하지 않았다면
            if (!visited[i])
                // dfs(cards, i, 0)
                dfs(cards, i, 0);
        }
        // list의 크기가 1이라면
        if (list.size() == 1)
            // 그대로 게임이 종료되므로 획득 점수 0 반환
            return 0;
        // list를 내림차순 정렬
        list.sort(Collections.reverseOrder());
        // 1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값을 반환
        return list.get(0) * list.get(1);
    }

    // dfs
    private void dfs(int[] cards, int index, int count) {
        // 이미 index에 방문했다면
        if (visited[index]) {
            // list에 count(상자의 수) 저장
            list.add(count);
            return;
        }
        // visited[i]를 true로 갱신
        visited[index] = true;
        // dfs(cards, cards[i] - 1, count + 1)
        dfs(cards, cards[index] - 1, count + 1);
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L079_131130 solution = new L079_131130();

        int[] cards = { 8, 6, 3, 7, 2, 5, 1, 4 };

        int result = solution.solution(cards);

        System.out.println(result);
    }
}