[SWEA] 1761 : 프로세서 연결하기

문제 >> 1761 프로세서 연결하기

//SWEA :: 1761 프로세서 연결하기
//2019-03-08
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Solution1767_2 {
 
    static int[][] map;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };// 상하좌우
    static int coreCnt, N, coreMax, lineMin;
    static ArrayList<pair> core;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine().trim());
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(bf.readLine().trim());
 
            map = new int[N][N];
            core = new ArrayList<>();
            coreCnt = 0; //전체 코어의 개수
            coreMax = Integer.MIN_VALUE;
            lineMin = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 1) {
                        if (i == 0 || i == N - 1 || j == 0 || j == N - 1)
                            continue; //가장자리 코어는 버린다
 
                        coreCnt++;
                        core.add(new pair(i, j)); //코어의 위치를 core리스트에 저장 
                    }
                }
            } // input
 
            setCore(0, 0, 0);
            System.out.println("#" + tc + " " + lineMin);
        } // end of tc
    } // end of main
 
    public static void setCore(int coreIdx, int sucCore, int lineLen) {
        if (coreIdx == coreCnt) { //모든 코어를 다 순회했을 때
            if (coreMax < sucCore) {
                coreMax = sucCore;
                lineMin = lineLen;
            } else if (coreMax == sucCore) {
                lineMin = lineMin > lineLen ? lineLen : lineMin;
            }
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            int ret = setLine(coreIdx, i);
            if (ret == -1) { // 전선 설치 실패
                setCore(coreIdx + 1, sucCore, lineLen);
            } else { // 전선 설치 성공
                setCore(coreIdx + 1, sucCore + 1, lineLen + ret);
                
                //Backtracking
                //전선 회수
                int ny = core.get(coreIdx).y;
                int nx = core.get(coreIdx).x;
                while (true) {
                    ny += dy[i];
                    nx += dx[i];
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1)
                        break; // 전원에 도달했을 경우
                    map[ny][nx] = 0; // 설치했던 전선을 회수한다.
 
                }
 
            }
        }
    }
 
    public static int setLine(int coreIdx, int dir) {
        ArrayList<pair> list = new ArrayList<>();
        pair cp = core.get(coreIdx);
        int ny = cp.y;
        int nx = cp.x;
        int lineLen = 0;
        while (true) {
            ny += dy[dir];
            nx += dx[dir];
            if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1)
                break; // 전원에 도달했을 경우
            if (map[ny][nx] != 0)
                return -1; // 전선 설치 실패
            list.add(new pair(ny, nx)); // 전선 설치할 위치 저장
 
            lineLen++;
        }
 
        // 전원 도달에 성공했을 때만 전선을 설치한다.
        for (pair p : list) {
            map[p.y][p.x] = 2;
        } // 전선 설치
 
        return lineLen; // 전선 길이 return
    } // end of setLine
 
    public static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
    }
 
}
 

처음엔 각 코어의 전선 설치 방향에 대한 모든 경우를 중복조합을 이용해 배열에 저장후

배열 값에 따라 전선을 설치하고, max/min 값을 갱신해가며 최종 답을 구하려고 했지만 시간 초과가 났다.

이유는 다음과 같다.

[0, 1, 2, 3] 을 각각 [상, 하, 좌, 우] 라고 생각한다면

코어가 7개 일때

[0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 1]

.

.

[3, 3, 3, 3, 3, 3, 3]

의 모든 경우에 대해 전선을 설치해볼 것이다.

하지만 같은 로직을 dfs를 이용해 구현한다면

[0, 0, 0, 0, 0, 0, 1] 해당하는 경우를 구한다음

     

     

[0, 0, 0, 0, 0, 0, 2] 를 구할때,

앞에 겹치는 부분인 [0, 0, 0, 0, 0, 0, X] 에 대한 부분은 볼 필요 없다.

즉 1방향으로 설치했던 전선을 회수하고

2 방향으로만 전선을 설치해보면 된다.

(내가 원래 짰던 코드에서는 앞의 0도 다시 순회를 했던 것 ..)

같은 완탐이어도 경우를 미리 구해놓고 하면 중복되는 케이스가 많아서 시간초과가 날수 있다는 것을 깨달았다 .

겹치는 케이스가 많다면 미리 구해놓지 말고 그때그때 dfs로 탐색하는 것이 시간을 줄일 수 있는 방법이다.