99클럽 코테 스터디 38일차 TIL + 혼자 놀기의 달인 (BFS)

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 혼자 놀기의 달인 (문제 링크)
• BFS

 

 

---

 

 

문제 설명

범희는 혼자서 숫자 카드 게임을 즐깁니다. 카드가 담긴 상자가 일렬로 나열되어 있으며, 각 상자에는 1부터 상자 개수까지의 번호가 적혀 있습니다. 범희는 임의의 상자를 골라 그 안에 있는 숫자를 확인하고, 그 숫자가 가리키는 상자를 연달아 열어가며 이미 열린 상자에 도달할 때까지 진행합니다.

이렇게 열린 상자들을 1번 상자 그룹이라 하고, 이 상자들을 제외한 나머지 상자들로 또다시 동일한 과정을 반복하여 2번 상자 그룹을 만듭니다. 이 두 그룹의 상자 수를 곱한 값이 범희가 얻을 수 있는 점수입니다. 범희가 얻을 수 있는 최고 점수를 구하는 프로그램을 작성하세요.

 

제한사항

• cards 배열의 길이는 2 이상 100 이하입니다.
• cards의 원소는 1 이상 cards의 길이 이하인 자연수입니다.
• cards 배열에는 중복되는 원소가 없습니다.

 

입출력 예

예제 1

cards = [8, 6, 3, 7, 2, 5, 1, 4]

• 1번 상자 그룹: [1, 4, 7, 8] → 길이: 4
• 2번 상자 그룹: [2, 5, 6] → 길이: 3
• 3번 상자 그룹: [3] → 길이: 1
• 결과: 최고 점수 = 4 x 3 = 12

 

 

---

 

 

문제 접근

1. 문제 이해
   • 각 상자에 담긴 카드 번호를 통해 이동하면서 상자 그룹을 형성합니다. 이를 BFS 방식으로 탐색하여 각 그룹의 크기를 구합니다.
   • 그룹 크기 리스트를 내림차순으로 정렬한 후, 가장 큰 두 그룹의 크기를 곱하여 최고 점수를 계산합니다.
2. 풀이 방법
   • BFS를 사용하여 상자 그룹을 탐색합니다. 각 상자 그룹이 형성되면 그룹의 크기를 리스트에 저장합니다.
   • 그룹 크기 리스트를 내림차순으로 정렬한 뒤, 상위 두 개의 크기를 곱하여 최대 점수를 반환합니다.

 

 

풀이 - Java 코드

import java.util.*;

class Solution {

    private boolean[] visited;
    private List<Integer> group = new ArrayList<>();
    private int[] box;

    public int solution(int[] cards) {
        visited = new boolean[cards.length];
        box = cards;
        for (int i = 0; i < box.length; i++) {
            int card = box[i];
            bfs(card - 1);
        }

        if (group.size() <= 1) {
            return 0;
        }

        Collections.sort(group, Collections.reverseOrder());

        return group.get(0) * group.get(1);
    }

    private void bfs(int index) {

        if (visited[index]) {
            return;
        }
        int count = 0;
        ArrayDeque<Integer> que = new ArrayDeque<>();
        que.add(index);
        while (!que.isEmpty()) {
            int idx = que.poll();
            if (visited[idx]) {
                continue;
            }
            visited[idx] = true;
            count++;
            que.add(box[idx] - 1);
        }

        group.add(count);
    }
}

풀이 설명

1. 초기화
   • visited 배열과 group 리스트를 초기화합니다.
   • 각 상자 그룹을 찾기 위해 BFS 탐색을 시작합니다.
2. BFS를 사용한 그룹 탐색
   • bfs(int index) 메서드는 주어진 인덱스에서 시작하여 그룹을 형성합니다.
   • 큐를 사용하여 상자를 순차적으로 방문하고, 그룹에 속한 상자의 수를 계산하여 group 리스트에 추가합니다.
3. 최대 점수 계산
   • 그룹 리스트를 내림차순으로 정렬하고, 상위 두 그룹의 크기를 곱하여 최대 점수를 계산합니다.
   • 그룹이 1개 이하라면, 0을 반환합니다.

 

 

---

 

 

마무리하며

이번 문제는 BFS를 사용해 그룹을 형성하고, 이를 통해 최대 점수를 계산하는 방식으로 해결하였습니다.