[프로그래머스 C#] Lv.2 혼자 놀기의 달인

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 놀이를 진행했을 때, 얻을 수 있는 최고 점수를 구하는 문제

- 1번 상자 x 2번 상자의 값이 최대가 되는 경우를 구해야 함

 

풀이 순서

1. 임의 선택 - 모든 상자 순회

2. 1번 상자 그룹 개수 찾기 

3. 임의 선택 - 열리지 않은 모든 상자 순회

4. 2번 상자 그룹 개수 찾기 

5. 1번 상자 x 2번 상자 값이 최고 점수라면 갱신

 

상자 그룹 개수 찾기

- 열어야 하는 상자가 이미 열려있을 때까지 상자를 열어야 함

- 이 때, 열게 된 상자의 개수가 상자 그룹의 개수가 됨

+ 2번 상자 그룹 개수를 탐색할 때, 1번 상자에서 이미 연 상자도 열려있는 상자

 

주석 참조

    using System;

    public class Solution
    {
        public int solution(int[] cards)
        {
            int answer = 0;

            // 1. 임의 선택 - 모든 상자 순회
            for (int i = 0; i < cards.Length; i++)
            {
                var boolArray1 = new bool[cards.Length]; // 1번 상자 그룹 방문배열

                // 2. 1번 상자 그룹 개수 찾기
                int count1 = Function(cards, boolArray1, i);

                // 3. 임의 선택 - 열리지 않은 모든 상자 순회
                for (int j = 0; j < cards.Length; j++)
                {
                    // 열려있는 상자는 탐색하지 않음
                    if (boolArray1[j])
                        continue;

                    var boolArray2 = boolArray1; // 2번 상자 그룹 방문배열

                    // 4. 2번 상자 그룹 개수 찾기
                    int count2 = Function(cards, boolArray2, j);

                    // 5. 최고 점수일 경우 갱신
                    int score = count1 * count2;
                    answer = Math.Max(answer, score);
                }
            }
            return answer;
        }

        // 상자 그룹의 개수를 구하는 메서드
        public int Function(int[] cards, bool[] boolArray, int currIndex)
        {
            int count = 0;
            while (boolArray[currIndex] == false)
            {
                boolArray[currIndex] = true;
                currIndex = cards[currIndex] - 1;
                count++;
            }
            return count;
        }
    }