[프로그래머스] 혼자 놀기의 달인 - Java

문제

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

프로그래머스

 

---

 

문제 개요

범희는 1부터 100까지의 숫자가 적힌 카드로 혼자 게임을 즐깁니다. 게임은 숫자 카드가 담긴 상자들을 무작위로 배치하고, 특정 상자를 선택하여 안의 숫자를 확인한 뒤, 그 숫자에 해당하는 상자를 열어가며 진행됩니다. 이미 열린 상자를 만나면 하나의 그룹이 형성되며, 같은 방식으로 다른 그룹을 만들어갑니다. 상자들은 모두 두 개의 그룹으로 나뉘며, 각 그룹의 크기를 곱한 값이 게임의 점수가 됩니다. 주어진 카드 번호 배열 cards에 따라 범희가 얻을 수 있는 최고 점수를 구하는 것이 목표입니다.

 

접근 방법

이 문제는 그래프 탐색의 형태를 가지고 있습니다. 각 상자와 그 안에 들어있는 숫자는 서로 연결된 형태를 이루며, 상자를 열어가며 하나의 연결된 그룹(컴포넌트)을 형성합니다. 문제의 목표는 주어진 카드 배열을 기반으로 가장 큰 두 개의 그룹을 찾아 그 크기의 곱을 최대화하는 것입니다.

• DFS 또는 BFS 사용: 각 상자에서 시작해 방문하지 않은 상자를 따라가며 그룹 크기를 계산.
• 두 개의 반복:
  1. 첫 번째 그룹을 탐색하며 방문 여부를 기록.
  2. 방문하지 않은 상자들 중 다시 탐색해 두 번째 그룹을 계산.
• 두 그룹의 크기를 곱해 최대 점수를 갱신.

import java.util.*;

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

        for (int start = 0; start < cards.length; start++) {
            boolean[] visit = new boolean[cards.length];

            // 첫 번째 그룹 탐색
            int group1Size = getGroupSize(cards, start, visit);

            // 두 번째 그룹 탐색
            for (int nextStart = 0; nextStart < cards.length; nextStart++) {
                if (!visit[nextStart]) { // 아직 방문하지 않은 상자만 탐색
                    int group2Size = getGroupSize(cards, nextStart, visit);
                    maxScore = Math.max(maxScore, group1Size * group2Size);
                }
            }
        }

        return maxScore;
    }

    private int getGroupSize(int[] cards, int start, boolean[] visit) {
        int count = 0;

        while (!visit[start]) {
            visit[start] = true;
            start = cards[start] - 1; // 다음 상자 이동
            count++;
        }

        return count;
    }
}