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

🧷 문제 링크

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

SW Expert Academy

 

📄 풀이 과정

문제 유형 : 완탐, 백트랙킹

• 가장 자리를 뺀 나머지 코어들을 list에 담아 연결할 코어의 리스트를 만든다.
• 순차적으로 코어를 하나씩 4방을 연결했을 때와 연결하지 않았을 때의 경우로 나눠 계산한다. 
  
  • 4방을 연결할 때는 그 방향으로 다른 전선이나(mat[r][c]=2) 다른 코어(mat[r][c]=1) 가 없는지 판단한 후, 없다고 판단이 된다면 연결한 후, 연결한 갯수를 return 한다.
  • 연결이 완료되면 다음 코어를 연결하러 이동한다.
  • 다른 모든 코어를 연결한 후 되돌아 왔을 때는 연결한 전선(mat[r][c]=2) 을 원래대로 복구(mat[r][c]=0) 한 후, 다음 방향으로 넘어간다.
  • 연결하지 않는 경우에는 아무런 연산없이 다음 코어로 넘어간다.
• 모든 코어를 연결했다면 (cnt==listCore.size()) 지금까지 연결한 코어의 갯수와 비교한다.
  • 현재 연결한 코어의 수가 지금까지 연결한 코어의 갯수보다 크다면, ans 와 갯수(maxCnt)를 현재로 갱신한다.
  • 같다면, 지금까지 구한 답과 현재 구한 답 중 작은 값으로 갱신한다.

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Solution_1767_프로세서연결하기 {
    
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    
    static int N, ans, maxCnt;
    static int[][] mat;
    static List<int[]> listCore;
    
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input_1767.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=T; tc++) {
            N = Integer.parseInt(br.readLine());
            mat = new int[N][N];
 
            listCore = new LinkedList<int[]>();        // 연결할 코어 리스트
            
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for(int j=0; j<N; j++) {
                    mat[i][j] = Integer.parseInt(st.nextToken());
                    // 가장 자리를 뺀 코어만 담음
                    if(i!=0 && i!=N-1 && j!=0 && j!=N-1 && mat[i][j]==1) listCore.add(new int[] {i, j});
                }
            }
            
            ans=Integer.MAX_VALUE; maxCnt=0;
            // 모든 프로세서를 순서대로 4방으로 놓아본다.
            go(0, 0, 0);
            sb.append("#").append(tc).append(" ").append(ans).append("\n");
            
        }
        
        System.out.print(sb.toString());
        br.close();
    }
    
    static void go(int idx, int cnt, int total) {    // 현재 연결할 코어 인덱스, 연결한 코어 갯수, 길이의 총합
        if(idx==listCore.size()) {        // 모든 코어를 연결했다면
            
            if(cnt>maxCnt) {
                ans = total;
                maxCnt = cnt;
            }else if(cnt==maxCnt) {
                ans = Math.min(ans, total);
            }
            return;
        }
        
        int[] core = listCore.get(idx);
        for(int d=0; d<4; d++) {
            // 4방향으로 전선을 놓는게 가능한지 판단
            if(isAvailable(core[0], core[1], d)) {    // 가능하다면
                int res = connect(core[0], core[1], d, 2);        // 연결하기 (2로 저장), 연결한 전선 갯수 return
                go(idx+1, cnt+1, total + res);                    // 다음 코어 연결
                connect(core[0], core[1], d, 0);                 // 되돌리기 (0으로 원상복구)
            }
        }
        
        // 현재 코어를 연결하지 않음, cnt와 total 변화없이 다음 코어로 이동
        go(idx+1, cnt, total); 
    }
    
    static boolean isAvailable(int r, int c, int d) {
        int nr = r, nc = c;
        while(true) {
            nr += dr[d];
            nc += dc[d];
            
            if(nr<0 || nr>=N || nc<0 || nc>=N) return true;        // 끝까지 도달함
            if(mat[nr][nc]==2 || mat[nr][nc]==1) return false;    // 다른 전선이나 다른 코어를 만남
        }
    }
    
    static int connect(int r, int c, int d, int status) {
        int nr = r, nc = c;
        int cnt=0;            // 연결한 전선의 갯수
        while(true) {
            nr += dr[d];
            nc += dc[d];
            
            if(nr<0 || nr>=N || nc<0 || nc>=N) return cnt;        // 끝까지 도달함
            mat[nr][nc] = status;                                // status 로 변경함
            cnt++;
        }
    }
    
 
}
 

 

 

📌 채점 결과