[SW Expert] [SW Test 샘플문제] 1767번 프로세서 연결하기 (Java)

SW Expert [SW Test 샘플문제] 1767번 프로세서 연결하기 :

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

 

 

상시 SW 역량테스트를 신청하기 전에 샘플문제로 풀어볼 수 있는 '프로세서 연결하기'이다.

최대한 많은 코어를 연결했을 때, 전선의 길이를 최소로 하는 값을 구하면 된다.

bfs로 할지, dfs로 할지 고민을 하다가

bfs로 하면 배열 복사에 시간과 메모리 소모가 너무 많을 듯 하여 dfs로 풀이하게 되었다.

 

입력을 받을 때 코어의 위치들을 ArrayList에 저장한다.

그 뒤 코어의 위치에서 상하좌우로 연결이 가능한지 체크를 한다. (isConnect 함수)

연결이 가능하다면 해당 방향으로 전선을 연결한 뒤, dfs 함수를 다시 한번 호출한다.

해당 코어를 연결 하지 않는 경우도 있으므로 백트래킹을 하여 다음 코어에 연결할 수 있게 해준다.

 

 

총 걸린 시간 : 1시간

난이도 : ★★★☆☆

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int n, core, answer, count;
    private static int[][] map;
    private static ArrayList<int[]> list;
    private final static int[] dx = {0, 0, -1, 1};
    private final static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            list = new ArrayList<>();
            map = new int[n][n];

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    map[i][j] = Byte.parseByte(st.nextToken());
                    if (map[i][j] == 1 && i != 0 && i != n - 1 && j != 0 && j != n - 1)
                        list.add(new int[]{i, j});
                }
            }

            core = 0; // 코어 수
            answer = 144; // 전선 수

            dfs(0, 0, 0);
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void dfs(int depth, int c, int line) {
        if (depth == list.size()) {
            if (core < c) {
                core = c;
                answer = line;
            } else if (core == c) {
                if (answer > line) answer = line;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (isConnect(list.get(depth), i)) { // 연결할 수 있는지 체크
                fill(list.get(depth), i, 2);
                dfs(depth + 1, c + 1, line + count); // 코어 선택 후 연결
                fill(list.get(depth), i, 0);
            }
        }
        dfs(depth + 1, c, line); // 코어 선택 안함
    }

    private static void fill(int[] index, int dir, int value) {
        count = 0;

        int x = index[0] + dx[dir];
        int y = index[1] + dy[dir];
        while (x >= 0 && y >= 0 && x < n && y < n) {
            map[x][y] = value;
            count++;
            x = x + dx[dir];
            y = y + dy[dir];
        }
    }

    private static boolean isConnect(int[] index, int dir) {
        int x = index[0] + dx[dir];
        int y = index[1] + dy[dir];

        while (x >= 0 && y >= 0 && x < n && y < n) {
            if (map[x][y] != 0) return false;
            x = x + dx[dir];
            y = y + dy[dir];
        }
        return true;
    }
}