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

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

SW Expert Academy

---

문제 해석

이 문제는 N x N 크기의 칩 위에 존재하는 여러 프로세서들을 칩의 가장자리에 연결하는 전선을 최적으로 설치하는 문제이다. 최대한 많은 프로세서를 연결하고, 그 중에서도 전선의 길이가 최소가 되도록 해야 한다. 프로세서가 가장자리에 위치할 경우 이미 연결된 것으로 간주하고 처리한다.

풀이 과정

솔루션은 깊이 우선 탐색(DFS)을 사용하여 모든 프로세서에 대해 가능한 모든 연결 방법을 탐색한다. 각 프로세서를 연결할 때, 상하좌우 방향으로 연결을 시도하고, 연결 가능한 상황에서는 전선을 설치한다. 이때, 설치된 전선의 길이와 연결된 프로세서의 수를 추적한다.

• dfs 함수는 현재 탐색 깊이를 기반으로 모든 프로세서를 체크하고, 가능한 모든 방향으로 연결을 시도한다.
• checkGo 함수는 특정 방향으로 계속해서 전선을 설치할 수 있는지를 검사한다.
• go와 back 함수는 전선을 설치하고 제거하는 기능을 수행하며, 설치 또는 제거된 전선의 길이를 반환한다.

코드

package edu.ssafy.im.SWEA.D0.No1767;

import java.io.*;
import java.util.*;

public class Solution {
    private int[][] graph; // 그리드 상태를 저장하는 배열
    private final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 네 방향을 나타내는 배열
    List<Point> searchList; // 탐색할 프로세서 리스트
    int n, ans, line, able, ableMax; // 칩 크기, 최소 전선 길이, 현재 전선 길이, 연결된 프로세서 수, 최대 연결 프로세서 수
    boolean[] flag; // 프로세서 연결 상태 플래그

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Solution().io();
    }

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int t = 1; t <= testCase; t++) {
            n = Integer.parseInt(br.readLine()); // 칩의 크기
            graph = new int[n][n]; // 그리드 초기화
            searchList = new ArrayList<>(); // 프로세서 리스트 초기화
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                    // 가장자리가 아닌 프로세서만 탐색 리스트에 추가
                    if (graph[i][j] == 1 && (i != 0) && (j != 0) && (i != (n - 1)) && (j != (n - 1))) {
                        searchList.add(new Point(i, j));
                    }
                }
            }
            ans = Integer.MAX_VALUE; // 최소 전선 길이 초기화
            flag = new boolean[searchList.size()]; // 연결 상태 초기화
            able = 0; // 연결된 프로세서 수 초기화
            ableMax = 0; // 최대 연결 프로세서 수 초기화
            line = 0; // 현재 전선 길이 초기화
            dfs(0); // DFS 탐색 시작
            sb.append("#").append(t).append(" ").append(ans).append("\n"); // 결과 문자열 추가
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void dfs(int depth) {
        if (depth == searchList.size()) {
            if (able > ableMax) {
                ableMax = able;
                ans = line;
            } else if (able == ableMax) {
                ans = Math.min(ans, line);
            }
            return;
        }

        // 현재 위치에서 가능한 모든 방향으로 연결 시도
        for (int i = 0; i < searchList.size(); i++) {
            if(searchList.size() - i + able < ableMax) return; // 가지치기: 최대 가능 연결 수가 현재 최대보다 적으면 중단
            if (!flag[i]) {
                int x = searchList.get(i).x;
                int y = searchList.get(i).y;
                for (int d = 0; d < direction.length; d++) {
                    if(!checkBranch(x, y, d)) continue; // 해당 방향으로 연결 가능한지 확인
                    int nx = x + direction[d][0];
                    int ny = y + direction[d][1];
                    if (checkStatus(nx, ny) && checkGo(nx, ny, d)) {
                        line += go(nx, ny, d); // 전선 설치
                        flag[i] = true;
                        dfs(depth + 1); // 다음 프로세서로 넘어감
                        flag[i] = false;
                        line -= back(nx, ny, d); // 설치한 전선 제거
                    } else {
                        flag[i] = true;
                        dfs(depth + 1); // 연결하지 않고 넘어감
                        flag[i] = false;
                    }
                }
            }
        }
    }

    // 전선 설치 가능 여부를 판단하는 함수
    private boolean checkBranch(int x, int y, int d) {
        // 해당 방향 끝까지 연결 가능한지 확인
        switch(d) {
            case 0:
                if(graph[x][y + direction[d][1] * (n - y - 1)] == 1) return false;
                if(graph[x][y + direction[d][1] * (n - y - 1)] == -1) return false;
                else return true;
            case 1:
                if(graph[x][y + direction[d][1] * y] == 1) return false;
                if(graph[x][y + direction[d][1] * y] == -1) return false;
                else return true;
            case 2:
                if(graph[x + direction[d][0] * (n - x - 1)][y] == 1) return false;
                if(graph[x + direction[d][0] * (n - x - 1)][y] == -1) return false;
                else return true;
            case 3:
                if(graph[x + direction[d][0] * x][y] == 1) return false;
                if(graph[x + direction[d][0] * x][y] == -1) return false;
                else return true;
            default:
                return false;
        }
    }

    // 전선 제거 함수
    private int back(int x, int y, int d) {
        graph[x][y] = 0; // 초기 상태로 복구
        int cnt = 1; // 제거된 전선 길이 카운트
        while (x != 0 && y != 0 && x != n - 1 && y != n - 1) {
            x += direction[d][0];
            y += direction[d][1];
            graph[x][y] = 0; // 전선 제거
            cnt++;
        }
        able--; // 연결된 프로세서 수 감소
        return cnt;
    }

    // 전선 설치 함수
    private int go(int x, int y, int d) {
        graph[x][y] = -1; // 전선 설치 상태 표시
        int cnt = 1; // 설치된 전선 길이 카운트
        while(x != 0 && y != 0 && x != n - 1 && y != n - 1) {
            x += direction[d][0];
            y += direction[d][1];
            graph[x][y] = -1; // 전선 설치
            cnt++;
        }

        able++; // 연결된 프로세서 수 증가
        return cnt;
    }

    // 전선 설치 가능 여부 검사 함수
    private boolean checkGo(int x, int y, int d) {
        if (x == 0 || y == 0 || x == n - 1 || y == n - 1) {
            return true; // 가장자리 도달 시 설치 가능
        }

        int nx = x + direction[d][0];
        int ny = y + direction[d][1];
        if (checkStatus(nx, ny))
            return checkGo(nx, ny, d); // 계속해서 전선 설치 가능 여부 재귀적으로 확인

        return false;
    }

    // 전선 설치 가능 지점 확인 함수
    private boolean checkStatus(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n && graph[x][y] == 0;
    }

    class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(4^k)로 추정할 수 있다, 여기서 k는 탐색해야 할 프로세서의 수이다. 각 프로세서마다 4가지 방향을 고려해야 하기 때문에 가능한 최악의 경우의 수가 이와 같다.

느낀점

이 문제를 통해 깊이 우선 탐색과 백트래킹을 사용하여 최적화 문제를 해결하는 방법을 심도 있게 연습할 수 있었다. 또한, 전선 설치와 제거의 과정에서 시뮬레이션하는 방법을 체계적으로 구현하는 경험을 할 수 있었다. 이러한 경험은 앞으로 더 복잡한 시뮬레이션 문제에 접근하는 데 도움이 될 것이다.