[알고리즘] 1767. 프로세서 연결하기

0. 문제

 

SW Expert Academy

 

---

1. 문제 이해

 

1. 부분 집합
2. 시뮬레이션

 

---

2. 제출

 

가. 오답

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

// 60 tc 중 58개 통과
public class SWEA1767 {
    static int N, ret;
    static int[][] map;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static List<Core> cores;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        int T = Integer.parseInt(st.nextToken());
        for(int tc=1; tc<=T; tc++){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            cores = new ArrayList<Core>();
            ret = 0;

            for(int i=0; i<N; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<N; j++){
                   map[i][j] = Integer.parseInt(st.nextToken());
                   if(map[i][j]==1){ // 코어면
                        cores.add(new Core(i, j));
                   }
                }
            }
            for(Core c : cores){ // 코어의 연결 가능한 전선이 수와 그 전선들의 길이 등 정보를 초기화
                c.find();
            }

            solve();
            sb.append("#").append(tc).append(" ").append(ret).append("\n");
        }

        System.out.println(sb);
        br.close();
    }
    private static void solve() {

        for(int i=0; i<cores.size(); i++){
            // 모든 코어 중 다음으로 연결할 코어 선택
            Core cur = null;
            Collections.sort(cores);

            for(int j=0; j<cores.size(); j++){
                cur = cores.get(j);
                if(cur.vis) continue;
                cur.vis = true;
                break;
            }

            if(cur.p == 0) continue; // 연결할 수 없는 코어
            ret += cur.line[cur.min]; // 전선 길이 추가

            // 전선 연결 표시
            int ny, nx;
            for(int j=1; j<N; j++){ 
                ny = cur.y + dy[cur.min]*j;
                nx = cur.x + dx[cur.min]*j;
                boolean under = ny<0||nx<0;
                boolean over = ny>=N||nx>=N;
                if(under||over) continue;
                if(map[ny][nx]==0)map[ny][nx] = 2;
            }
            // 전선 깔고서 코어의 정보 갱신
            for(int j=0; j<cores.size(); j++){
                if(cores.get(j).vis) continue;
                cores.get(j).find();
            }

            //debug
            // System.out.println("------------" + i);
            // for(int y=0; y<N; y++){
            //     for(int x=0; x<N; x++){
            //         System.out.print(map[y][x] + " ");
            //     }
            //     System.out.println();
            // }
        }
    }

    static class Core implements Comparable<Core> {
        boolean vis = false;
        int y, x;
        int p, min; // 각 코어마다 연결 가능한 전선의 수, 가장 짧은 연결 가능한 전선의 인덱스
        int[] line = new int[4]; // 시계방향(상우하좌) 연결에 필요한 전선의 길이

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

        public void find(){
            p = 0; min = 0;
            int ny, nx;
            for(int d=0; d<4; d++){ // 4방 탐색하며 p, line, min을 설정
                for(int i=1; i<N; i++){ // 끝까지
                    ny = y + dy[d]*i;
                    nx = x + dx[d]*i;
                    boolean under = ny<0||nx<0;
                    boolean over = ny>=N||nx>=N;
                    if(under||over) continue;
                    if(map[ny][nx]>0) { // 코어, 전선을 만남
                        this.line[d] = Integer.MAX_VALUE; // 연결할 수 없음
                        break; 
                    }
                    this.line[d] = i; // 시계방향으로 전선의 길이를 측정
                }
                if(line[d]!=Integer.MAX_VALUE) p++; // 연결할 수 있는 전선이 수 세기 
                if(line[min] > line[d]) min = d; // 가장 짧은 전선의 인덱스
            }
        }

        @Override
        public int compareTo(Core o) {
            if(this.p == o.p){
                return Integer.compare(this.line[this.min], o.line[o.min]);
            }
            return Integer.compare(this.p, o.p);
        }

        @Override
        public String toString() {
            return "Core [vis=" + vis + ", y=" + y + ", x=" + x + ", p=" + p + ", min=" + min + ", line="
                    + Arrays.toString(line) + "]";
        }

    }
}

근본 없이 풀었다.

 

완탐으로 풀면 비효율적이라고 생각해서 그랬다.

 

---

나. 완전 탐색으로 풀기

 

1. 각 코어는 상, 하, 좌, 우 + “연결하지 않기”로 5가지 상태 중 하나를 선택해야 한다.
2. DFS로 모든 경우의 수를 탐색해서 답을 찾는다.

 

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

public class SWEA1767_2 {
    // 멕시노스 크기, 최대코어수, 비가장자리코어수, 최소 전선 길이합
    static int N, max, totalCnt, min;
    static int[][] map;
    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,1,0,-1};
    static ArrayList<int[]> list; // 비가장자리 코어 리스트
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        for(int tc=1; tc<=T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            list = new ArrayList<int[]>();
            max = 0;
            totalCnt = 0;
            min = Integer.MAX_VALUE;

            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if(i>0 && i<N-1 && j>0 && j<N-1 && map[i][j]==1) {
                        list.add(new int[] {i,j});
                        totalCnt++;
                    }
                }
            } // 멕시노스 셀 정보 입력 및 비가장자리 코어리스트 생성

            solve(0, 0, 0);
            System.out.println("#"+tc+" "+min);
        }

    }

    static void solve(int idx, int cCnt, int lCnt) {// 현재 코더, 코어갯수, 전선길이 합
        if(cCnt+(totalCnt-idx)<max) return; // 남은 모든 코어를 더해도 최대 코어개수를 갱신할 수 없으면 가지치기

        if(idx==totalCnt) {
            if(max < cCnt) { // 코어의 수가 최대
                max = cCnt;
                min = lCnt;
            }else if(max == cCnt) {
                if(min > lCnt) {
                    min = lCnt;
                }
            }
            return;
        }

        int[] cur = list.get(idx);
        int y = cur[0];
        int x = cur[1];
        // 4방 탐색
        for(int d=0; d<4; d++) {
            if(isAvailable(y, x, d)) {
                int len = setStatus(y, x, d, 2); // 전선 놓는 경우
                solve(idx+1, cCnt+1, lCnt+len);
                setStatus(y, x, d, 0); // 원복
            }
        }
        // 전선 안 놓는 경우
        solve(idx+1, cCnt, lCnt);
    }

    static boolean isAvailable(int y, int x, int d) {
        int ny = y;
        int nx = x;
        while(true) {
            ny += dy[d];
            nx += dx[d];
            boolean under = ny<0||nx<0;
            boolean over = ny>=N||nx>=N;
            if(under||over) return true;
            if(map[ny][nx] > 0) return false;
        }
    }

    static int setStatus(int y, int x, int d, int s) { // map[y][x]의 d 방향으로 이동하며 s로 상태 변경
        int ny = y;
        int nx = x;
        int cnt = 0;
        while(true) {
            ny += dy[d];
            nx += dx[d];
            boolean under = ny<0||nx<0;
            boolean over = ny>=N||nx>=N;
            if(under||over) break;
            map[ny][nx] = s;
            cnt++;
        }
        return cnt;
    }
}

 

---

 

진짜 일부의 유명한 그리디 알고리즘을 제외하고선 완전탐색으로 풀자.
주어진 시간 안에 문제를 풀어야 하는데 머리 아프게 고민할 시간이 없다.
근본 있게 풀기.