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

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

 

📌 풀이 과정

최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구해야 한다.
단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하는 것이 문제 조건이다.

가장자리에 위치한 core는 전선을 연결하지 않기에 전선 연결에서 고려하지 않아도 된다.
따라서 가장자리에 있는 core는 코어 목록에서 제외해도 된다.

✨ 제출 코드

메모리 : 22,048 kb
시간 : 196 ms

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


public class Solution {

    static int N, minLength, maxCore;
    static int[][] map;
    static List<int[]> coreInfo;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine()); // 배열의 크기
            map = new int[N][N];
            coreInfo = new ArrayList<>();
            minLength = Integer.MAX_VALUE;
            maxCore = 0;

            for(int i = 0; i < N; i++) {
                StringTokenizer 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) {
                        coreInfo.add(new int[]{i, j});
                    }
                }
            }

            connect(0, 0, 0);
            System.out.println("#" + t + " " + minLength);
        }
    }

    private static void connect(int idx, int length, int core){
        if(idx == coreInfo.size()){
            if(core > maxCore) {
                maxCore = core;
                minLength = length;
            }
            else if(core == maxCore){
                minLength = Math.min(minLength, length);
            }
            return;
        }

        int x = coreInfo.get(idx)[0];
        int y = coreInfo.get(idx)[1];

        for(int[] d : dir) {
            int nx = x; int ny = y;
            int count = 0;
            while(true){
                nx += d[0];
                ny += d[1];
                count++;

                if(nx < 0 || nx >= N || ny < 0 || ny >= N || map[nx][ny] != 0) break;

                if(nx == 0 || ny == 0 || nx == N-1 || ny == N-1){
                    nx = x; ny = y;
                    for(int i = 0; i < count; i++){
                        nx += d[0];
                        ny += d[1];
                        map[nx][ny] = 2;
                    }
                    connect(idx + 1, length + count, core + 1);

                    map[nx][ny] = 0;
                    for(int i = 0; i < count-1; i++){
                        nx -= d[0];
                        ny -= d[1];
                        map[nx][ny] = 0;
                    }
                    break;
                }
            }
        }
        connect(idx + 1, length, core);
    }
}

 

처음에 connect 메서드 기저 조건으로

if (length > minLength) return; 조건문을 넣어줘서 계속 fail이 떴다...

문제에서 최대한 많은 core를 연결하되, 가장 짧은 전선 길이를 구하는 것이 핵심인 것을 알고 있었지만

 

그 사실을 망각하고 실행시간 줄여보겠다고 저 조건문을 넣는순간

코어가 많든 적든 minLength 보다 큰 전선길이면 무조건 컷 하는... 비정상적인 로직이었다 😓

 

그리고 두달 전엔, 조합을 곁들여서 문제를 풀었다.

 

---

📌 조합을 활용한 풀이

1. 최대한 많은 core에 전원 연결하기

주어진 Core의 개수를 M개라고 하면, 최대한 많은 코어에 전원을 연결해야 한다.
M개 중 M개를 뽑는 조합부터 시작하여 M-1개, M-2개, …, 0개까지 차례대로 조합을 만든다.

2. mCr개의 코어를 고른 후 DFS 탐색

상하좌우 방향으로 전선을 만들 수 있는지 탐색한다.

• 전선을 만들 수 있는 경우
  재귀적으로 다음 Core로 넘어가서 전선을 연결한다.
  현재 조합의 모든 Core에 대한 전선을 연결한 후, 최소 전선의 길이 합을 갱신한다.
• 전선을 만들 수 없는 경우
  DFS 탐색을 중단하고, 다음 Core 조합으로 넘어간다.

 

✨ 제출 코드

메모리 : 25,068 kb

시간 : 137 ms

조합으로 연결한 코어의 갯수가 많은 경우일때 부터 탐색을 시작하기 때문에

특정 조합의 코어 탐색을 마치면, 무조건 최소 길이를 계속해서 갱신해주면 된다.

+ 상대적으로 빠른 실행 시간인 것을 확인할 수 있다.

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

public class Solution {

    static int N, min;
    static int[][] map;
    static boolean[] selected;
    static List<int[]> core;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t = 1; t <= T; t++){
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            core = new ArrayList<>(); // 코어 위치 저장하는 리스트
            min = Integer.MAX_VALUE;

            for(int i = 0; i < N; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j = 0; j < N; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());

                    // 가장자리가 아닌 코어만 리스트에 추가
                    if(map[i][j] == 1 && i > 0 && i < N-1 && j > 0 && j < N-1) {
                        core.add(new int[]{i, j});
                    }
                }
            }

            selected = new boolean[core.size()];
            for(int i = core.size(); i >= 0; i--){
                combination(0, 0, i);
                if(min < Integer.MAX_VALUE) break;
            }

            System.out.println("#" + t + " " + min);
        }
    }

    static void combination(int cnt, int start, int pick){
        if(cnt == pick){
            dfs(0, 0);
            return;
        }

        for(int i = start; i < core.size(); i++){
            selected[i] = true;
            combination(cnt + 1, i + 1, pick);
            selected[i] = false;
        }
    }

    static void dfs(int idx, int wire){
        if(idx == core.size()) {
            min = Math.min(min, wire); // 최소 전선 길이 합으로 갱신
            return;
        }

        if(!selected[idx]) { // 부분 집합에 포함되지 않는 코어는 넘어감
            dfs(idx + 1, wire);
            return;
        }

        for(int i = 0; i < 4; i++){
            int x = core.get(idx)[0];
            int y = core.get(idx)[1];
            int length = 0;
            boolean success = false;

            while(true){
                x += dx[i]; y += dy[i];
                if(x < 0 || x >= N || y < 0 || y >= N) { // 범위 끝에 도착했으면 성공
                    success = true;
                    break;
                }
                if(map[x][y] != 0) break; // 전선이나 코어를 만나면 실패
                map[x][y] = 2; // 전선
                length++;
            }

            if(success) dfs(idx + 1, wire + length);

            while(true){ // 원상복구
                x -= dx[i]; y -= dy[i];
                if(x == core.get(idx)[0] && y == core.get(idx)[1]) break;
                map[x][y] = 0;
            }
        }
    }


}