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

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 

SW Expert Academy

[제약 사항]
1. 7 ≤  N ≤ 12
2. Core의 개수는 최소 1개 이상 12개 이하이다.
3. 최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.

[입력]
입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어지며 그 다음 줄부터 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 N값이 주어지며, 다음 N줄에 걸쳐서 멕시노스의 초기 상태가 N x N 배열로 주어진다.
0은 빈 cell을 의미하며, 1은 core를 의미하고, 그 외의 숫자는 주어지지 않는다.

[출력]
각 테스트 케이스마다 '#X'를 찍고, 한 칸 띄고, 정답을 출력한다.
(X는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

입력
3  
7    
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 0 1 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
9  
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
11 
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 1 0 0
0 1 0 1 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

 

출력
#1 12
#2 10 
#3 24 

접근 방식

핵심 키워드

멕시노스의 가장 자리에는 전원이 흐르고 있다.

=> 코어 위치를 찾으면서 가장 자리 부분에 있는 코어는 제외

Core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며, 전선은 절대로 교차해서는 안 된다.

=> 직선으로 선을 연결해보자! 가다가 전선을 만나면 그 경우의 수는 제외

최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합

=> 부분 집합으로 많이 연결했을 때 경우의 수가 성공하면 거기서 종료

 

제약사항 중 코어의 개수는 최대 12개

=> 부분 집합으로 연결 될 수 있는 코어의 경우의 수를 모두 찾아본다.

풀이 요약

1. 부분 집합을 만든다.

2. 연결 할 수 있는지 확인하는 메서드를 만든다. (DFS 형식)

=> 이때 매개 변수로 2차원 배열을 계속 clone 해서 넘겨주었다. 

=> 이렇게 안하고 넘길 때 선을 그었다 돌아와서 선을 다시 지워도 된다.

 

전체코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution_No15_프로세서연결하기 {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "r=" + r +
                    ", c=" + c +
                    '}';
        }
    }
    static int N, coreSize, res;
    static int[][] map;
    static LinkedList<Point> corePos;
    static int[] pick, dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int testCase = 1; testCase <= T; testCase++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            corePos = new LinkedList<>();
            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());
                    // 가장 자리에 있지 않은 코어 찾아서 리스트에 저장
                    if (!(i == 0 || j == 0 || i == N - 1 || j == N - 1) && map[i][j] == 1) corePos.add(new Point(i, j));
                }
            }
            coreSize = corePos.size();
//            System.out.println(corePos);
            //// 입력 완료
            /*
            완탐 돌리기
            이미 연결된 애들 제외 무조건 개수로 카운트
            1. 부분 집합 만들어서 가능한 조합 만들어낸다.
            2. 각 코어마다 선을 연결해본다.
             */
            res = Integer.MAX_VALUE;
            for (int i = coreSize; i >= 1; i--) {
                pick = new int[i];
                subSet(0,0, i);
                if (res != Integer.MAX_VALUE) {
                    break;
                }
            }
            System.out.println("#" + testCase + " " + res);
        }
    }
    private static void subSet(int start, int cnt, int size){
        if (cnt == size) {
            /// 부분 집합 구하기 완료 -> 모두 연결해본다.
            int[][] copyMap = copy(map);
            connect(0, copyMap, 0);
            return;
        }
        for (int i = start; i < coreSize; i++) {
            pick[cnt] = i;
            subSet(i+1, cnt+1, size);
        }
    }
    /*
    코어를 4방 중 한 곳으로 연결한다
    연결된다면 재귀로 다음 코어로
    음 맵을 복사해서 쓴다? 너무 메모리 많이 먹나?
    일단 하자
     */
    private static void connect(int coreNum, int[][] copyMap, int sum){
    /// 저장해둔 코어 수보다 커지면 dfs 끝 return
        if (coreNum >= pick.length) {
            res = Math.min(res, sum);
            return;
        }
        Point curPos = new Point(corePos.get(pick[coreNum]).r, corePos.get(pick[coreNum]).c);
        for (int dir = 0; dir < 4; dir++) {
            int[][] curMap = copy(copyMap);
            int dist = 0;
            int nr = curPos.r;
            int nc = curPos.c;
            while (true) {
                nr = nr + dr[dir];
                nc = nc + dc[dir];
                if (isIn(nr, nc) && curMap[nr][nc] == 0) {
                    curMap[nr][nc] = 1;
                    dist++;
                }
                // 끝까지 간거니까 성공 다음 코어로
                else if(!isIn(nr, nc)) {
                    connect(coreNum+1, copy(curMap), sum+dist);
                    break;
                }
                /// 이외에는 코어나 전선을 만난거라 더 못가고 다음으로 break
                else break;
            }
        }
    }
    // 2차원 배열 클론
    private static int[][] copy(int[][] map){
        int[][] copyMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();
        }
        return copyMap;
    }
    // 범위 내에 값인지 확인
    private static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N;
    }
}