[SWEA] 프로세서 연결하기 (Java)

다시 풀어도 접근법을 생각 못했던 문제 ... 😭

• 문제 링크
  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&

• 변수 정보

  • map : 모든 코어 정보가 저장된 변수
  • coreInfo : 가장자리를 제외한 모든 코어 정보가 저장된 변수
  • coreCnt : 가장자리를 제외한 모든 코어 수
  • dx, dy : 방향 정보
  • min, max : 가장자리를 이을 수 있는 코어의 개수가 최대(max)이면서 그 길이의 합이 (min)인 정보를 담고 있는 변수

• 접근법

  • dfs 재귀 함수를 이용한 풀이
    dfs 함수의 매개변수 정보
    • idx = 현재 순회한 코어 아이디
    • cnt = 현재 가장자리에 연결된 코어 수
    • len = 현재 가장자리에 연결된 전선 길이 합
      
      

  1. idx == coreCnt
     모든 코어를 조회한 경우이므로, 현재 cnt, len을 각각 max, min과 비교함
     만약 cnt가 max보다 크다면 max, min을 각각 cnt, len으로 갱신해줘야함.
     cnt와 max가 같다면, len < min인 경우 min을 len으로 갱신.
  2. idx < coreCnt
     현재 idx의 코어를 각 4방향 (상하좌우)으로 가장자리까지 전선을 이어봐야함.
     • 변수 정보
       count : 현재 방향으로 가장자리까지 이은 전선 길이
       ox, oy : 원래 코어 좌표
       tx, ty : temp 좌표

  tx, ty를 현재 방향으로 1씩 움직이면서 가장자리까지 잇는 과정을 반복. count도 1씩 추가
  만약 중간에 전선이나 코어를 만나는 경우 count = 0으로 초기화 후 반복문 종료
  그렇지 않은 경우 가장자리를 만나면 반복문 종료
  반복문이 종료되면 count만큼 현재 방향을 기준으로 map에 전선을 1로 표시

  • 전선을 이을 수 있는 경우 (count!=0)
    dfs(idx+1, cnt+1, len+count) 실행
    (코어수 1증가, 길이 count만큼 증가)
    위의 함수가 종료되면, 다음 방향의 전선을 체킹하기 위해서 전선으로 표시했던 것을 다시 0으로 초기화 (count만큼 map에 0으로 표시)
  • 전선을 이을 수 없는 경우 (count==0)
    dfs(idx+1, cnt, len) 실행
    (코어수 동일, 길이 동일)

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

class Pair {
    int y, x;
    Pair(int y, int x) {this.y = y; this.x = x;}
}

public class Solution {

    static int N, coreCnt, min, max;
    static int[][] map;

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    static Pair[] coreInfo;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/n1767.txt"));
        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];
            visited = new int[N][N];
            coreInfo = new Pair[N * N];
            coreCnt = 0;
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++)
                    // map에 모든 코어 정보를 저장하고, coreInfo에 가장자리를 제외한 코어 정보 저장하기
                    if ((map[i][j] = Integer.parseInt(st.nextToken())) == 1 && !isEdge(i, j)) coreInfo[coreCnt++] = new Pair(i, j);
            }

            dfs(0, 0, 0);

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

    static void dfs(int idx, int cnt, int len) {

        // 종료 조건 : 코어의 개수만큼 돌았을 때
        if(idx == coreCnt) {
            if(max < cnt) { // 연결할 수 있는 코어 개수가 더 많은 경우
                max = cnt;
                min = len;
            } else if (max == cnt) { // 코어 개수가 같은 경우
                if(min > len) min = len;
            }
            return;
        }

        int y = coreInfo[idx].y;
        int x = coreInfo[idx].x;

        for(int i=0;i<4;i++) {
            // 연결선 길이
            int count = 0;
            // 원래 x, y좌표
            int oy = y;
            int ox = x;
            // temp x, y
            int ty = y;
            int tx = x;

            while(true) {
                ty += dy[i];
                tx += dx[i];
                // 벽을 만나면 break
                if(!isValid(ty, tx)) break;
                // 중간에 코어나 전선을 만나는 경우
                if(map[ty][tx] == 1) {
                    count = 0; break;
                }
                count++;
            }

            // count 크기만큼 전선으로 표시
            for(int j=0;j<count;j++){
                oy+=dy[i];
                ox+=dx[i];
                map[oy][ox] = 1;
            }

            if(count == 0) dfs(idx+1, cnt, len);            // 전선을 연결할 수 없는 코어
            else {                                              // 전선을 연결할 수 있는 코어
                dfs(idx + 1, cnt + 1, len + count);

                // 위의 dfs 함수가 종료되면 전선을 없애고 초기화하기 (다른 방향의 전선을 체킹하기 위함)
                oy = y;
                ox = x;
                for(int j=0;j<count;j++){
                    oy+=dy[i];
                    ox+=dx[i];
                    map[oy][ox] = 0;
                }
            }


        }

    }

    static boolean isEdge(int y, int x) {
        return y == 0 || x == 0 || y == N-1 || x == N-1;
    }

    static boolean isValid(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < N;
    }
}