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

🔔 문제

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

🎯 풀이방법

• N : cell의 크기 (7 ≤ N ≤ 12)
• cell : core와 전선을 담을 맵
• minWireLength : 최소 전선길이의 합
• maxCore : 최대 core의 갯수 (0 ≤ maxCore ≤ 12)
• coreList : core 위치(행, 열)을 담을 List
• dx (열), dy (행) : 상, 하, 좌, 우

1. 입력받은 cell이 core라면
      1-1. 가장자리에 있는 core이면 coreList에 저장 X
      1-2. 아니라면 coreList에 저장 O

2. 전선을 연결하는 DFS (startConnect)
parameter : 현재 위치(idx), 현재 core 갯수(coreCnt), 현재 전선합(wireCnt)

① 현재 core 위치 가져오기

② 해당 core의 위치에서 사방 탐색(상, 하, 좌, 우)
      ③ 한 방향으로 나아갔을 때 범위를 벗어나면 다른 코어나 전선을 만나지 않는다를 의미함 → break
      ④ 가는 도중에 다른 코어 or 전선을 만났으면 방향을 바꿔서 다시 카운팅
      ⑤ ③,④가 아니라면 전선 길이 1 증가

⑥ 카운팅이 없다면 인덱스만 1 증가해서 DFS
⑦ 카운팅이 되었다면 해당 정보를 누적해서 DFS

💡 이 문제를 통해 얻어갈 것

완전탐색 (DFS) + 시뮬레이션 문제

💻 Java 코드

메모리 24,344 kb, 실행시간 709ms, 코드길이 2,778

import java.util.*;
import java.io.*;
 
class Solution
{
    static class Core {
        int x,y;  // 열, 행
 
        public Core(int y, int x) {
            this.y = y;
            this.x = x;
        }   
    }
     
    static int N, cell[][], minWireLength, maxCore;
    static int dx[] = {0,0,-1,1}; // 상 하 좌 우
    static int dy[] = {-1,1,0,0};
    static List<Core> coreList; // 코어 위치 담을 리스트
     
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            N = Integer.parseInt(br.readLine());
             
            cell = new int[N][N];
            coreList = new ArrayList<>();
             
            // 입력
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<N; j++) {
                    int in = Integer.parseInt(st.nextToken());
                    if(in==1) {
                        cell[i][j] = in;
                         
                        // 가장자리에 있는 코어라면 리스트에 저장X
                        if(i==0 || j==0 || i==N-1 || j==N-1)
                            continue;
                        coreList.add(new Core(i,j));  // 행, 열
                    }
                     
                }
            }
             
            minWireLength = Integer.MAX_VALUE;
            maxCore = Integer.MIN_VALUE;
             
            startConnect(0,0,0);
             
            sb.append("#"+t+" "+minWireLength+"\n");
        }
         
        System.out.println(sb.toString());
    }
     
    public static void startConnect(int idx, int coreCnt, int wireCnt) {
        if(idx == coreList.size()) {  
            if(maxCore < coreCnt) { // 최대한 많은 core에 연결
                maxCore = coreCnt;
                minWireLength = wireCnt;
            } else if(maxCore == coreCnt) { // 전선길이의 합이 최소가 되는 값
                minWireLength = Math.min(wireCnt, minWireLength);
            }
            return;
        }
         
        // 인덱스 위치의 코어의 좌표
        int x = coreList.get(idx).x;
        int y = coreList.get(idx).y;
         
        // 상 하 좌 우 탐색
        for(int dir=0; dir<4; dir++) {
            int count=0, nx=x, ny=y;
             
            while(true) {
                nx += dx[dir];
                ny += dy[dir];
                 
                // 범위를 벗어났다 is 다른코어나 전선을 만나지 않음
                if(ny<0 || ny>=N || nx<0 || nx>=N) {
                    break;
                }
                 
                // 가는 길에 다른 코어 혹은 전선 존재 -> 다른 방향으로
                if(cell[ny][nx] == 1) {
                    count = 0;
                    break;
                }
                 
                // 어떠한 방해도 없다면 +1
                count++;
            }
 
            // count 갯수만큼 1로 채워줌
            int fill_x = x;
            int fill_y = y;
             
            for(int i=0; i<count; i++) {
                fill_x += dx[dir];
                fill_y += dy[dir];
                cell[fill_y][fill_x] = 1;
            }
             
            if(count==0)
                startConnect(idx+1, coreCnt, wireCnt);
            else {
                startConnect(idx+1, coreCnt+1, wireCnt+count);
                 
                // 원본맵을 다시 0으로 되돌림
                fill_x = x;
                fill_y = y;
                 
                for(int i=0; i<count; i++) {
                    fill_x += dx[dir];
                    fill_y += dy[dir];
                    cell[fill_y][fill_x] = 0;
                }
            }
        }
    }
}