SWEA 1767 [프로세서 연결하기]

SW Expert Academy 프로세서 연결하기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE

//SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다.

안녕하세요. 이번 문제는 SW Expert Academy의 [프로세서 연결하기] 입니다.

BOJ 15683 [감시] 가 떠오르는 문제네요.

제출하면 계속 1~2개의 테스트케이스가 통과하지 않았습니다.

그 이유는 프로세서를 전원에 연결할 수 없는 경우에만 depth를 늘렸기 때문이었습니다.

프로세서를 가만히 내버려두는 경우를, 4방향 연결 가능 확인 전에  DFS로 추가해 주니 통과할 수 있었습니다.

결과값을 저장해 나갈 땐,  배열을 이용해서 해당 코어만큼 연결될 때의 최저값을 저장했습니다.

import java.util.*;
 
public class Solution {
    public static int T;
    public static int N;
    public static int[][] Map = new int[12][12];
    public static ArrayList<int[]> processor = new ArrayList<int[]>();    //프로세서 좌표 
    public static int[] result = new int[13];    // i :연결된 코어 개수 . [i] :연결된 전선 개수   
    public static int Max_power;    // 최대 연결된 코어 
    public static int[][] d = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
    public static void DFS(int depth, int power, int plus) {
        if(depth == N) {
            if(power >= Max_power) {
                Max_power = power;
                if(result[power] > plus) {
                    result[power] = plus;
                }
            }
            return;
        }
        int i = processor.get(depth)[0];
        int j = processor.get(depth)[1];
        if(i == 0 || i == N-1 || j == 0 || j == N-1) {
            DFS(depth + 1, power + 1, plus);
            return;
        }
        DFS(depth + 1, power, plus);     // 그냥 연결 안해버리
        for(int k = 0; k < 4; k++) {    // 연결 가능한지 확인해보고 연결하기 
            int dist = 0;
            switch(k) {
            case 0: {    // up
                dist = i;
                break;
            }
            case 1: {    //down
                dist = N - i - 1;
                break;
            }
            case 2: {    //right
                dist = N - j - 1;
                break;
            }
            case 3: {    //left
                dist = j;
                break;
            }
            }
            boolean is_end = true;
            for(int l = 1; l <= dist; l++) {
                if(Map[i + l * d[k][0]][j + l * d[k][1]] != 0)
                    is_end = false;
            }
            if(is_end) {
                for(int l = 1; l <= dist; l++) {
                    Map[i + l * d[k][0]][j + l * d[k][1]] = 2;
                }
                DFS(depth + 1, power + 1, plus + dist);
                
                for(int l = 1; l <= dist; l++) {
                    Map[i + l * d[k][0]][j + l * d[k][1]] = 0;
                }
            }
            
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for(int t = 1; t <= T; t++) {
            N = sc.nextInt();
            Max_power = 0;
            for(int i = 0; i <= N; i++)
                result[i] = 144;
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    Map[i][j] = sc.nextInt();
                    if(Map[i][j] == 1) {
                        int[] p = new int[2];
                        p[0] = i;
                        p[1] = j;
                        processor.add(p);
                    }
                }
            }
            DFS(0, 0, 0);
            System.out.println("#" + t + " " + result[Max_power]);
            processor.clear();
        }
    }
}