C# [프로그래머스] Lv.2 카펫

 

 

문제 설명

 

 

 

 

 

 

제한 사항 및 입출력 예

 

 

 

 

프로그래머스의 완전 탐색 계열 문제로 카페트의 색깔을 바탕으로 내부 색깔의 갯수와 외부 색깔의 갯수에 따라 카페트의 크기가 얼마나 되는지 return 해야 하는 문제이다.

 

그래프의 알고리즘 중 하나인 깊이 우선 탐색(DFS)를 이용해 완전 탐색을 진행하고 다음 분기로 넘어가는 방식으로 코드를 작성했다.

 

 

public class Solution 
{
    // 깊이 우선 탐색(DFS) 메서드 정의
    public void dfs(int height, int brown, int yellow, int[] arr) 
    {
        // height가 노란색 격자 양옆을 감싸는 갈색 격자의 수. 초기화 값은 2, 재귀할 때마다 2씩 추가
        int inner = ((brown - height) / 2 - 2) * (height / 2);
        
        // 만약 inner가 노란색 격자 수와 같다면
        if (inner == yellow) {
            // arr 배열의 첫 번째 원소에 갈색 격자의 가로 길이를 저장
            arr[0] = (brown - height) / 2;
            // arr 배열의 두 번째 원소에 갈색 격자의 세로 길이를 저장
            arr[1] = height / 2 + 2;
        } else {
            // 조건을 만족하지 않으면 height를 2 증가시키고 재귀 호출
            dfs(height + 2, brown, yellow, arr);
        }
    }

    // 주어진 갈색 격자와 노란색 격자의 수를 기반으로 카펫의 크기를 찾는 메서드
    public int[] solution(int brown, int yellow) 
    {
        // 결과를 저장할 배열 초기화
        int[] answer = new int[2];
        // 초기 height를 2로 설정하고 dfs 메서드 호출
        dfs(2, brown, yellow, answer);
        // 계산된 결과를 반환
        return answer;
    }
}

 

 

갈색 카페트가 노란색 카페트를 둘러싸려면 상단과 하단에 한줄씩은 필요하기 때문에 최소한의 카페트의 높이(초기값)는 2로 설정한다. 

 

그리고 Dfs를 수행할 메서드를 만들고 각각의 색깔 격자를 담은 변수들과 중앙의 노란색 카페트 색깔을 계산할 inner 변수를 선언해준다.

 

inner변수는 중앙의 yellow 색깔 카페트의 갯수와 같아질때 까지 DFS를 재귀하는데  해당 값이 yellow와 일치하지 않는다면 같아질때 까지 height를 증가시키면서 재귀해나간다.

 

내부 격자를 재귀해 나가는 구조와 재귀 하면서 수행할 수식을 짜는 과정이 조금 어려웠지만 구조를 잡고 난 후에는 생각보다 어렵지 않은 문제였다.