[SWEA/SW Test 샘플] 1767. 프로세서 연결하기 - JAVA 자바

• 129ms
• 구현 DFS

최대한 많은 코어를 전원에 연결할 경우, 필요한 전선 길이의 합의 최소를 구하는 문제이다. 단, 전선끼리 교차할 수 없다.

 

(x,y) 좌표에서의 코어가 (x, 0), (x, n-1), (0, y), (n-1, y) 까지 전선을 설치할 수 있는지, 설치할 수 있는 경우에서 전선의 길이가 최소로 되는 방향으로 설치할 수 있도록 한다.

 

1. 가장자리가 아닌 코어들의 좌표를 리스트에 저장

2. 코어 리스트를 하나씩 돌며 상하좌우 탐색하며 전선을 설치할 수 있는 방향을 찾은 후 방문처리하며 DFS 탐색 진행

    2-1. 방문처리하며 진행하다가 중간에 끊겨 해당 방향으로 전선을 설치할 수 없다면 코어의 좌표까지 다시 되돌아가며 방문처리 해제

3. 전선을 설치할 수 있는 방향이 있다면 전선 길이의 합에 + 후 다음 인덱스 상하좌우 탐색 → 2번으로

4. 모든 코어를 다 확인했다면 전선을 연결한 코어의 최대 & 전선 합의 최소가 되는지 구한다.

5. 백트래킹

 

# 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Solution {
    static List<int[]> cores = new ArrayList<int[]>();
    static int n, max = 0, minLen = Integer.MAX_VALUE;
    static boolean[][] visited;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    // 해당 방향으로 전선을 이을 수 있는지 체크 후 길이 출력
    public static int calcLen(int x, int y, int d) {
        int len = 0;
        int tmpx = x, tmpy = y;
        while (true) {
            tmpx += dx[d];
            tmpy += dy[d];
            if (tmpx >= 0 && tmpx < n && tmpy>= 0 && tmpy < n) {
                if (!visited[tmpx][tmpy]) {
                    len++;
                    visited[tmpx][tmpy] = true;
                } else {
                    // 중간에 끊겼다면 지금까지 방문표시한 것들 해제
                    while(true) {
                        tmpx -= dx[d];
                        tmpy -= dy[d];
                        if(tmpx == x && tmpy == y) break;
                        visited[tmpx][tmpy] = false;
                    }
                    return -1;
                }
            } else
                break;
        }
        return len;
    }

    public static void backtrace(int x, int y, int d) {
        while (true) {
            x += dx[d];
            y += dy[d];
            if (x >= 0 && x < n && y >= 0 && y < n)
                visited[x][y] = false;
            else
                break;
        }
    }

    public static void dfs(int index, int count, int length) {
        if (index == cores.size()) {
            if (max < count) {
                minLen = length;
                max = count;
            } else if (max == count) {
                minLen = Math.min(minLen, length);
            }
            return;
        }
        for (int d = 0; d < 4; d++) {
            int nx = cores.get(index)[0];
            int ny = cores.get(index)[1];

            int len = calcLen(nx, ny, d);
            if (len == -1) {
                continue; // 이 방향은 안돼
            } else {
                // 전선을 포함한 경우
                dfs(index + 1, count + 1, length + len);
                backtrace(nx, ny, d);

            }
        }
        // 전선을 포함하지 않은 경우
        dfs(index + 1, count, length);
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            cores.clear();
            n = Integer.parseInt(br.readLine());
            visited = new boolean[n][n];
            minLen = Integer.MAX_VALUE;
            max = 0;
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    if (Integer.parseInt(st.nextToken()) == 1) {
                        if (i != 0 && i != n - 1 && j != 0 && j != n - 1)
                            cores.add(new int[] { i, j }); // 가장자리 코어가 아니라면 코어 리스트에 저장
                        visited[i][j] = true;
                    }
                }
            }

            dfs(0, 0, 0);
            sb.append('#').append(t).append(' ').append(minLen).append('\n');
        }
        System.out.println(sb);
    }
}