완전탐색 알고리즘

카펫

해당 문제는 완전탐색 알고리즘의 문제로.. 사실 완전 탐색에 대해서 공부를 한적이 없어서 처음에 어떻게 접근할까 고민하다가 이틀정도 고민 끝에 해답을 찾을 수 있었습니다. 난이도는 그렇게 어려운 편이 아니라고 하지만.. 역시 수포자한테는 힘들었던 문제였습니다.... 풀이를 봐도 전혀 이해를 못하다가 결국 그림을 그리면서 패턴을 찾아서 풀었습니다.

위의 문제에서 접근법을 찾을 수 있는 힌트는 가로의 길이가 세로의 길이보다 크거나 같다는 전제 조건을 캐치하는것과 갈색 벽돌이 빨간색 벽돌을 둘러쌓야하는 것을 이해하였다면 접근방법을 이해하는데 시간이 단축 될 것 입니다.

먼저, 갈색 벽돌의 개수는 카펫의 위, 아래 가로 길이가 같고, 세로 길이 역시 좌, 우가 같기 때문에 (2 * y) + (2 * x) - 4라는 방정식으로 갈색 벽돌의 개수를 구할 수 있습니다. 여기서 - 4는 가로, 세로 길이가 아무리 변해도 카펫의 꼭지점의 개수는 4개로 변하지 않는 불변의 값을 가집니다.

그리고 빨간색 벽돌의 세로 길이는 갈색 벽돌의 세로 길이보다 -2만큼 이고, 가로 길이 역시 갈색 벽돌 -2 정도이기 때문에 (y - 2) * (x - 2) 식을 도출할 수 가 있습니다.

갈색 벽돌과 빨간색 벽돌의 개수를 이용하여 카펫의 가로, 세로의 길이를 구할 수 있었습니다.

JAVA 코드로 다음과 같이 작성 할 수 있습니다.

import java.util.Arrays;

public class Carpet {

    public int[] solution(int brown, int red){

        if(brown < 8 ||brown >5000 && red < 1 || red >2000000) {
            throw new IllegalStateException();
        }

        int[] answer = new int[2];
        // 빨간색 벽돌은 갈색벽돌에 둘러 쌓여 있기 때문에 세로의 길이는 무조건 3이상부터 시작한다.
        // 가로 길이도 마찬가지로 갈색 벽돌이 빨간색 벽돌을 둘러쌓기 위해서는 3이상이여 됩니다.
        A:for (int y = 3; y < 5000; y++) {
            for (int x = y; x < 5000; x++) {
                if(isSameAsBrown(y, x, brown)){
                    if(isSameAsRed(y, x, red)){
                        answer[0] = x;
                        answer[1] = y;

                        break A;
                    }
                }

            }
        }
        return answer;
    }

    // 세로의 길이 : y, 가로의 길이 : x, 갈색 벽돌 개수 : brown 을 argument로 받아서 가로 세로의 길이를 구하기 위한 로직
    public static boolean isSameAsBrown(int y, int x, int brown){

        //위 아래로 가로 길이는 같고, 좌 우 가로 길이는 같기 때문에 갈색 벽돌의 개수는 아래의 식으로 구할 수 있습니다.
        //가로 세로의 길이에 따라서 변하지 않는 점은 결국 꼭지점은 항상 4개이기 때문에 -4를 해주어야 합니다.
       if((((y * 2) + (x * 2)) - 4) == brown){

            return true;
        }

        return false;
    }

    // 마찬가지로 빨산색 벽돌의 수를 가지고 가로 세로의 길이를 구합니다.
    public static boolean isSameAsRed(int y, int x, int red){
        //가로 -2 * 세로 - 2를 하면 빨간색 벽돌의 넓이가 나옵니다.
        if(((y - 2) * (x - 2)) == red){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        Carpet carpet = new Carpet();
        System.out.println(Arrays.toString(carpet.solution(10,2)));
        System.out.println(Arrays.toString(carpet.solution(8,1)));
        System.out.println(Arrays.toString(carpet.solution(24,24)));
    }
}

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.util.Arrays;

import static org.junit.Assert.*;

@RunWith(JUnit4.class)
public class CarpetTest {

    @Test
    public void 완전탐색_카펫_테스트() {
        //given
        Carpet carpet = new Carpet();

        //when
        int[] tesCase1 = carpet.solution(8, 1);
        int[] tesCase2 = carpet.solution(10, 2);
        int[] tesCase3 = carpet.solution(24, 24);

        //then
        assertEquals("[3, 3]", Arrays.toString(tesCase1));
        assertEquals("[4, 3]", Arrays.toString(tesCase2));
        assertEquals("[8, 6]", Arrays.toString(tesCase3));
    }
}

위의 소스코드에서 이중 포문에서 첫번째 포문을 A로 alias를 설정하여 break문으로 해당 포문을 한번에 빠져나갈 수 있는 문법입니다.

A:for (int y = 3; y < 5000; y++) {
    // 비즈니스로직 구현부
} 

처음 써보는건데 유용해서 한번 써봤습니다.