[BOJ - JAVA] 17829 - 222 풀링 (분할 & 정복)

# 주소

https://www.acmicpc.net/problem/17829

17829번: 222-풀링

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    static int n;
    static int[][] arr;
    static int[][] ans;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        dfs(n,n);
    }
    static void dfs(int a, int b){
        ans = new int[a/2][b/2];
        for(int i = 0; i < a/2; i++){
            for(int j = 0; j < b/2; j++){
                ans[i][j] = check(2 * i,2 * j);
            }
        }
        if(a / 2 == 1 && b / 2 == 1){
            System.out.println(ans[0][0]);
        }else {
            arr = new int[a/2][b/2];
            arr = ans.clone();
            dfs(a / 2, b / 2);
        }
    }
    static int check(int x, int y){
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = x; i < x + 2; i++)
            for(int j = y; j < y + 2; j++) {
                list.add(arr[i][j]);
            }
        Collections.sort(list);
        return list.get(2);
    }
}

분할 정복 문제를 푼게 이번이 2번째입니다.

중요성을 모르고 지내왔는데 그래도 재귀를 이해하는데 있어 알아두면 좋을 것 같아 풀었습니다.

난이도는 실버3?인가 실버2여서 푸는데 딱히 오래걸리지 않았습니다. 살펴봅시다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n][n];
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        arr[i][j] = scan.nextInt();
    }
}
dfs(n,n);

arr를 이중 for문으로 입력받겠습니다.

그리고 dfs에 (n,n)을 파라미터로 집어넣겠습니다.

static void dfs(int a, int b){
    ans = new int[a/2][b/2];
    for(int i = 0; i < a/2; i++){
        for(int j = 0; j < b/2; j++){
            ans[i][j] = check(2 * i,2 * j);
        }
    }

dfs의 내부 구조는 다음과 같습니다.

파라미터로 가져온 n과 n을 a, b로 갖고오겠습니다.

그리고 2중 for문으로 check함수를 실행할텐데요.

그 전에, a/2, b/2크기의 ans배열을 선언할거에요.

이 ans배열의 크기가 1이 될 때 정답이 되게 만들 것이고 2x2크기에서 두 번째로 큰 값들의 모임이 될 것이에요.

그럼 check()함수는 어떻게 생겼을까요

static int check(int x, int y){
    ArrayList<Integer> list = new ArrayList<>();
    for(int i = x; i < x + 2; i++)
        for(int j = y; j < y + 2; j++) {
            list.add(arr[i][j]);
        }
    Collections.sort(list);
    return list.get(2);
}

저는 check()함수의 파라미터로 2 * i, 2 * j를 넣었어요.

그렇게 해야 모든 인덱스를 탐색할 수 있어서 그렇습니다.

그리고 파라미터로 가져온 것을 x, y로 담고 이것을 ArrayList에 담을 것입니다.

이중 for문을 통해서말이지요.

이 이중for문의 범위는 x ~ x + 2까지, y ~ y + 2까지 탐색할 것입니다.

자연스럽게 총 4번의 탐색이 이루어지고 이것을 오름차순으로 정렬한 뒤 세번째의 인덱스 값을 return하면 2번째로 큰 값들만 ans[i][j]에 담기게 되는 것이지요.

그럼 다시 dfs 내부로 돌아옵니다.

if(a / 2 == 1 && b / 2 == 1){
    System.out.println(ans[0][0]);
}else {
    arr = new int[a/2][b/2];
    arr = ans.clone();
    dfs(a / 2, b / 2);
}

자 여기에서 만약 a/2 , b / 2가 1이 되면 arr[0][0]을 출력하면 그것이 정답이 되겠죠?

하지만 그렇지 않을 경우엔 arr를 ans의 값들로 그대로 복붙하고 dfs를 다시 실행해줍니다.

물론 a와 b의 크기를 2로 나눈채로요.

이 과정을 계속하면서 1이 될때까지 2로 나누면 되겠습니다.

감사합니다.