출저는 문제 링크입니다.
대략 설명을 드리면 2차원 배열이 있고(. 이랑 X로 표현)
그 배열에서 최대 정사각형의 변의 길이를 구하라는 문제인데요
. . . . . .
. X. . . .
. . . . . . <- 요런 4 * 6 배열의 경우 4을 아웃풋으로 뽑으라는 문제입니다. (굻게 표시된 점)
X. . . . .
(X 의 좌표를 계속 주고 이때 최대 길이를 구하라고 하지만 중요하진 않으니 스킵)
제가 생각한 알고리즘이 있기는 한데 이게 맞는 접근 방법인지 봐주시기 바랍니다.
--- (분할) ---
일단 문제의 크기를 4개로 나눕니다. 가로, 세로를 반으로 쪼개서 재귀함수에 넣습니다.
--- (반환) ---
위에처럼 쪼개는 연산을 반복해서 크기가 1이 될때까지 이어갑니다.
1이 되면 하나의 좌표가 나오는대 이 좌표에 해당하는 배열값이 만약 . 이라면 1을 반환하고 X 라면 0을 반환합니다.
반환 단계는 그냥 이정도로만 간단히 나옵니다.
--- (통합) ---
이제부터가 쫌 골때리는 통합단계인데요.
그 전에 먼저 함수 설명을 드리자면
square square_caculate(int startX, int startY, int endX, int endY) // (여기서 square는 정사각형의 시작 좌표와 길이, 사분면의 위치를 담고있습니다)
{
if(startX == endX && startY == endY) { // 반환 단계
if(배열[startX][startY] == '.') return~;
else return~;
}
square1 = square_caculate(...); //분할 단계
square2 = square_caculate(...);
square3 = square_caculate(...);
square4 = square_caculate(...);
. //통합단계
.
.
}
이런식으로 구성할려고 하고 있습니다.
그래서 통합 단계에서는 4분할 한 각 영역의 최대 정사각형에 대해 조사를 합니다.
만약 1사분면에서 최대 길이가 3이 나왔다면 오른쪽 아래 대각선 방향으로,
2사분면에서 최대 길이 4가 나왔다면 왼쪽 아래, 3사분면은 왼쪽 위... 이런 방식으로 조사를 진행합니다.
이렇게 조사를 진행 해서 최대 길이가 나오는 구조체 square를 반환합니다.
여기서 조사한다는건 어쩔수 없이 브루트포스로 검사하고요.
그래서 이런식으로 알고리즘을 짜볼려구 하는데
제가 접근하는 방법이 맞는지, 혹시라도 틀렸으면 알맞은 알고리즘좀 알켜주시면 고맙겠습니다~~
ps: 알고리즘 혼자공부는 쫌 어렵네여..
특히 외국 알고리즘 문제들은.. ㄷㄷㄷ
ps2: 제가 분할 정복이랑 구조체를 쓴 이유는, 요 두 개를 써야 솔루션이 된다고 하네요..(위 링크 보시면 옆에 태그가 있습니다)
