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

 

 

만약 이러면...? 만약 이러면?...에 빠졌던 문제 ㅋㅋㅋ

 

한 core가 선을 뻗어있는 상태에서

다른 core가 침범하는 방향이 답이면 이전 core의 선을 치워야하나?...

 

그 답은 아래에 ^^...

 

 

---

1. 출처

---

 

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

SW Expert Academy

 

• 테두리 부근에 core가 있다면 이미 전기가 연결된 것이다.
• core들은 4방으로 선을 뻗을 수 있다.
• 최대한 많은 core의 선을 연결하고, 최소의 core 선 값을 도출해라

 

 

---

2. 설계

---

 

• core 위치를 저장한다. (단, 테두리에 있는 core는 제외한다. 이미 연결되어 있기 때문이다.)
• core 위치를 가지고 Permutation을 돌릴 것이다. (상상상상, 상상상하, 상상하하 . . . . 이런 식으로 가짓수를 도출하기 위함이다.)
• 선을 그릴 수 있는지 판단하고, 선을 2로 표시한다. (다른 프로세서가 선을 그을 때 겹치는지 확인하기 위함이다.)
• 다른 방향 조사를 위해 Permutation에서 나왔다면 2라는 선을 지우고 0으로 다시 채워준다. (원복)
• 가장 많은 core가 연결되었다면 core 수와 len을 갱신해준다. 하지만 core수가 max값과 같으면 len 길이가 짧을 때 갱신해준다.

 

 

---

3. 전체 코드

---

 

/*
* Memory : 25,588 KB
* Time : 242 ms
* */

import java.util.*;
import java.io.*;

public class Solution{
    static int N;
    static int[][] map;
    static List<Loc> core;
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    static int max_conn;
    static int min_len;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int T=1; T<=t; T++){

            //초기화
            max_conn = 0;
            min_len = 987654321;
            core = new ArrayList<>();

            N = Integer.parseInt(br.readLine());

            map = new int[N][N];

            for(int r=0; r<N; r++){
                String info = br.readLine();
                StringTokenizer st = new StringTokenizer(info, " ");
                for(int c=0; c<N; c++){
                    map[r][c] = Integer.parseInt(st.nextToken());

                    //core 위치
                    if((r!=0 && c!=0 && r!=N-1 && c!=N-1) && map[r][c]==1){
                        core.add(new Loc(r, c));
                    }
                }
            }

            //입력 끝

            Permutation(0, 0, 0);

            System.out.println("#"+T+" "+min_len);
        }//test
    }

    public static void Permutation(int depth, int conn, int len){

        if(depth == core.size()){
            
            if(max_conn<conn){
                min_len = len;
                max_conn = conn;
            }
            
            if(max_conn==conn){
                if(min_len>len){
                    min_len = len;
                    max_conn = conn;
                }
            }
            
            return;
        }

        
        for(int d=0;d<4;d++){
            if(FillPossible(d, core.get(depth).r, core.get(depth).c)){
                int count = Fill(d, core.get(depth).r, core.get(depth).c, 2); //그리기
                Permutation(depth+1, conn+1, len+count);
                Fill(d, core.get(depth).r, core.get(depth).c, 0); //지우기
            }
        }
        Permutation(depth+1, conn, len); //선택 안함
    }

    public static boolean FillPossible(int d, int startR, int startC){
        
        int count = 1;
        while(true){
            int nextR = startR + drc[d][0]*count;
            int nextC = startC + drc[d][1]*count;
            if(nextR<0 || nextR>=N || nextC<0 || nextC>=N) return true;//연결 가능
            if(map[nextR][nextC]!=0) return false; //연결 불가능

            count++;
        }
        
    }

    public static int Fill(int d, int startR, int startC, int num){
        
        int count = 1;
        while(true){
            int nextR = startR + drc[d][0]*count;
            int nextC = startC + drc[d][1]*count;

            if(nextR<0 || nextR>=N || nextC<0 || nextC>=N) break;

            map[nextR][nextC] = num;

            count++;
        }

        return count-1;
    }

    public static class Loc{
        int r;
        int c;
        public Loc(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}