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

문제

• SWEA 1767
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

1. 모든 코어의 좌표를 담은 리스트 coreList를 생성한다. 가장자리일 경우는 이미 전원이 연결되어 있기때문에 제외한다.
2. 현재 코어에서 전선을 설치 할 수 있는지 보는 install()함수를 호출한다.
   2-1. 현재 코어에서 4방향을 탐색하면서 전선을 연결할 수 있는지 확인하기 위해 dfs()함수를 호출한다.
   2-2. dfs()에서 탐색하는 방향, 좌표값을 받아 전선을 연결완료할 때 까지 계속 재귀호출한다. 만약, 중간에 범위를 벗어나거나 0이 아니면 전선을 연결할 수 없는 경우이므로 이 방향으로는 전선을 연결할 수 없기 때문에 함수를 빠져나온다.
   2-3. 2-1에서 4방향 탐색을 해주지 않고 현재 코어를 선택하지 않는 경우도 있기 때문에 for문 밖에 다음 코어 설치를 확인하기 위한 install()함수를 호출해주어야 한다.
3. 이렇게 탐색방향에 따른 각각의 경우의 수에 따라 insatll함수에 온 idx가 코어 개수만큼 된다면 모든 코어를 체크한 것으로 이때의 전선 길이의 합을 구한다.
   단, 주의할 점은! 앞에서 구한 코어 개수 `maxCores`보다 현재 연결한 코어 개수가 더 많을 경우에 전선 길이의 합을 변경한다
   만약 코어 개수가 같다면 그 중 더 작은 값을 Ans에 넣어준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
class Solution {
 
    static int T, N, M;
    static int[][] map;
    static List<Point> coreList; // 코어리스트
    static int[] di = { -1, 1, 0, 0 }; // 상하좌우
    static int[] dj = { 0, 0, -1, 1 };
    static int maxCores; //직접 연결한 코어 개수
    static int Ans;//전선 개수
 
    static class Point {
        int x, y;
 
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
 
            map = new int[N][N];
            int[][] tmp = new int[N][N]; // 코어 연결할때마다 상태 저장 임시배열
            coreList = new ArrayList<>();
            Ans = Integer.MAX_VALUE;
            maxCores = Integer.MIN_VALUE;
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    tmp[i][j] = map[i][j];
 
                    if (map[i][j] == 1 && ((i!=0) && (i != N - 1) && (j!=0) && (j != N - 1))) {
                        coreList.add(new Point(i, j));
                    }
                }
            } // End input
 
             
            install(0, 0, tmp, 0);
            sb.append("#"+tc+" "+Ans+"\n");
        } // End testCase
        System.out.println(sb+"");
 
    }
 
    private static void install(int idx, int sum, int[][] tmp, int coreCnt) { // 코어 인덱스, 전선 길이 합, 임시맵
         
        if(idx >= coreList.size()) { //모든 코어 체크 완료
            if(maxCores < coreCnt) {
                maxCores = coreCnt;
                Ans = sum;
            }
             
            if(maxCores == coreCnt) Ans = Math.min(Ans, sum);
            return;
        }
         
        // 현재 코어에서 4방향 연결 가능한지
        int nowX = coreList.get(idx).x;
        int nowY = coreList.get(idx).y;
        for (int d = 0; d < 4; d++) dfs(idx, nowX, nowY, d, 1, sum, tmp, coreCnt);
        
        install(idx+1, sum, tmp, coreCnt); //★현재 코어 선택안하고 넘기자
    }
 
    private static void dfs(int idx, int nowX, int nowY, int d, int cnt, int sum, int[][] tmp, int coreCnt) {
         
        int nx = nowX + di[d];
        int ny = nowY + dj[d];
         
        if (nx < 0 || ny >= N || ny < 0 || ny >= N || tmp[nx][ny] != 0) {
            return;
        }
 
        tmp[nx][ny] = -2; //전선 표시
        if (nx==0 || nx == N - 1 || ny==0 || ny == N - 1) { // 연결완료
            sum += cnt;
            install(idx+1, sum, tmp, coreCnt+1); //다음 코어 체크
            tmp[nx][ny] = 0;
            return;
        }
 
        dfs(idx, nx, ny, d, cnt+1, sum, tmp, coreCnt); //전선 연결
        tmp[nx][ny] = 0;
    }
}