[SW Test 샘플문제] 프로세서 연결하기 - JAVA

 

[SW Test 샘플문제] 프로세서 연결하기

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

삼성에서 개발한 최신 모바일 프로세서 멕시노스는 가로 N개 x 세로 N개의 cell로 구성되어 있다.

1개의 cell에는 1개의 Core 혹은 1개의 전선이 올 수 있다.

멕시노스의 가장 자리에는 전원이 흐르고 있다. Core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며,

전선은 절대로 교차해서는 안 된다. 초기 상태로는 아래와 같이 전선을 연결하기 전 상태의 멕시노스 정보가 주어진다.

(멕시노스의 가장자리에 위치한 Core는 이미 전원이 연결된 것으로 간주한다.)

**▶ 최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.

단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.**

위 예제의 정답은 12가 된다.

 

[제약 사항]

\1. 7 ≤ N ≤ 12

\2. Core의 개수는 최소 1개 이상 12개 이하이다.

\3. 최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.

 

[입력]

입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어지며 그 다음 줄부터 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 N값이 주어지며, 다음 N줄에 걸쳐서 멕시노스의 초기 상태가 N x N 배열로 주어진다.

0은 빈 cell을 의미하며, 1은 core를 의미하고, 그 외의 숫자는 주어지지 않는다.

 

[출력]

각 테스트 케이스마다 '#X'를 찍고, 한 칸 띄고, 정답을 출력한다.

(X는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

 

풀이

시키는대로 하면 되는 쉬운 문제였습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
​
public class Main {
    static int t,n;
    static int map[][];
    static int cnt = 0;
    static Node[] core;
    static int core_cnt;
    static boolean visited[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int max = 0;
    static int max_len = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        t = Integer.parseInt(br.readLine());
        int ans_cnt = 1;
        while(t-->0) {
            max = 0;
            max_len = 0;
            n = Integer.parseInt(br.readLine());
            map = new int[n][n];
            visited = new boolean [n][n];
            core_cnt = 0;
            
            for(int i=0; i<n; i++) {
                String [] t = br.readLine().split(" ");
                for(int j=0; j<n; j++) {
                    map[i][j] = Integer.parseInt(t[j]);
                    if(map[i][j]==1) {
                        core_cnt++;
                    }
                }
            }
            core = new Node[core_cnt];
            int tmp = 0;
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(map[i][j]==1) {
                        visited[i][j] = true;
                        if(i==0 || i==n-1 || j==0 || j==n-1) {
                            core[tmp] = new Node(i,j,true);
                            tmp++;
                        }
                        else {
                            core[tmp] = new Node(i,j,false);
                            tmp++;
                        }
                        
                    }
                }
            }
            dfs(0,0,0);
            System.out.println("#"+ans_cnt+" "+max_len);
            ans_cnt++;
        }
        
    }
    public static void dfs(int level, int sum, int len) {
        if(level == core_cnt) {
            if(max<sum) {
                max = sum;
                max_len = len;
                return ;
            }
            else if(max ==sum) {
                max_len = Math.min(max_len, len);
                return ;
            }
            else {
                return ;
            }
        }
        Node now_core = core[level];
        int x = now_core.x;
        int y = now_core.y;
        boolean flag  =now_core.flag;
        
        if(flag) {
            dfs(level+1,sum+1,len);
        }
        else {
            for(int i=0; i<4; i++) {
                if(isPossible(x,y,i)) {
                    int tmp_len = fill(x,y,i);
                    dfs(level+1,sum+1,len+tmp_len);
                    flush(x,y,i);
                }
            }
            
            dfs(level+1,sum,len);   // 안채우고 그냥 보내보기
        }
        
        
    }
    
​
    
    
    
    public static int fill(int x, int y, int dir) {
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        int cnt = 0;
        while(isRange(nx,ny)) {
            visited[nx][ny] = true;
            nx+=dx[dir];
            ny+=dy[dir];
            cnt++;
        }
        return cnt;
    }
    public static void flush(int x, int y, int dir) {
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        while(isRange(nx,ny)) {
            visited[nx][ny] = false;
            nx+=dx[dir];
            ny+=dy[dir];
        }
    }
    public static boolean isPossible(int x, int y, int dir) {
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        
        while(isRange(nx,ny)) {
            if(visited[nx][ny] || map[nx][ny]==1) {
                return false;
            }
            nx+=dx[dir];
            ny+=dy[dir];
        }
        
        return true;
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<n && y<n) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y;
    boolean flag;
    Node(int x, int y, boolean flag){
        this.x=x;
        this.y=y;
        this.flag = flag;
    }
}
​