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

링크

SWEA[1767]

문제설명

• 4방향 전선 연결, 전선충돌x, 최대코어, 최소전선길이

문제풀이

• 4방향 완전탐색

문제코드

package swea;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution1767 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int Len=Integer.MAX_VALUE;
    public static int Core=Integer.MIN_VALUE;
    public static int Ltemp=0;
    public static int Ctemp=0;

    public static int N;
    public static int[][] map;

    public static LinkedList<int[]> Corerc = new LinkedList<int[]>();

    public static void Search(int cnt) {
        if(cnt==Corerc.size()) {
            if(Core<Ctemp) {
                Core=Ctemp;
                Len=Ltemp;
            }
            else if(Core==Ctemp) {
                if(Len>Ltemp) {
                    Len=Ltemp;
                }
            }
            return;
        }

        int[] now = Corerc.get(cnt);
        int len=0;
        for (int d = 0; d < 4; d++) {
            len = connectable(now, d);
//            코어 연결 가능할 때,
            if(len>=1) {
                connect(now,d,len);
                Ctemp++;
                Ltemp+=len;
                Search(cnt+1);
                del_connect(now,d,len);
                Ctemp--;
                Ltemp-=len;
            }
        }
        Search(cnt+1);
    }

    public static int connectable(int[] now, int now_dir) {
        int len=0;

        int sr=now[0];
        int sc=now[1];

        int nr;
        int nc;

        while(true) {
            nr = sr + dir[now_dir][0]; 
            nc = sc + dir[now_dir][1]; 
//            경계 안이면
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
//                전선 설치가능할경우
                if(map[nr][nc]==0) {
//                    한칸 이동
                    sr=nr;
                    sc=nc;
                    len++;
                }
//                이미 코어나 전선이 있음
                else {
                    return -1;
                }
            }
//            경계 밖으로 넘어가면(전기연결됨)
            else {
                return len;
            }
        }
    }

    public static void connect(int[] now, int now_dir, int len) {
        int nr;
        int nc;
        for (int i = 1; i <= len; i++) {
            nr=now[0]+i*dir[now_dir][0];
            nc=now[1]+i*dir[now_dir][1];
            map[nr][nc]=2;
        }
    }

    public static void del_connect(int[] now, int now_dir, int len) {
        int nr;
        int nc;
        for (int i = 1; i <= len; i++) {
            nr=now[0]+i*dir[now_dir][0];
            nc=now[1]+i*dir[now_dir][1];
            map[nr][nc]=0;
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/1767.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb;

        int T = Integer.parseInt(br.readLine());

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

            N = Integer.parseInt(br.readLine());
            map = new int[N][N];

            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());
                }
            }

//            가장자리 코어는 무시
            for (int i = 1; i < N-1; i++) {
                for (int j = 1; j < N-1; j++) {
                    if(map[i][j]==1)Corerc.add(new int[] {i,j});
                }
            }


            Ltemp=0;
            Ctemp=0;
            Search(0);

            sb = new StringBuilder();
            sb.append("#").append(test_case).append(" ").append(Len);            
            System.out.println(sb);
//            초기화
            Len=Integer.MAX_VALUE;
            Core=Integer.MIN_VALUE;
            Corerc.clear();
        }
    }
}

아쉬운점

• 인덱스 실수
  • dir[0], dir[1] 구분안했음
• 모든 Core를 연결하는 방법으로 재귀 짰었음
  • Core연결 못하면 그냥 패스하고 다른 코어 연결경우의 수 체크해야됨
• 전기 연결 가능성 체크할 때, 이미 전선이나 코어 만나면 못한다고 해야됨. 되는 길이 리턴했었음.
• 코어갯수 안 세아려줬음
  -Ctemp++안해줬음
• 코어갯수가 크면 무조건 Len 갱신해야함.
  • 이전 코어 갯수의 Len을 유지하는 경우 생겼었음...
• 4방탐색끝나고 연결한번이라도 됐으면 연결안하는 경우의 수 고려 안했었음.
  • 그리디한풀이임. 연결하는게 무조건 좋다는 생각X
  • 연결이 되는경우라도 연결안하는 경우가 더 나은 답이 나올 수 있음.

  • 7
    0 0 0 0 0 1 0
    0 0 0 0 0 1 1
    0 0 0 0 0 1 0
    1 1 1 0 0 0 0
    0 1 0 0 0 0 0
    0 0 0 0 0 0 0
    0 0 0 0 0 0 0

  • 8임 10이아니라

잘한점

• O(N)
  • 12^2*4방향 최대 24칸
• 문제조건 제대로 고려했음
  • 가장자리코어 고려x
  • 전선,코어만나면 연결못함
  • 최대코어갯수
  • 최소전선길이
• 연결 가능성 체크하는 함수를 boolean이아니라 int로 해서 메서드 좀더 편하게 만듬

시간 고려

• Core정보를 LinkedList에 저장했을때랑 Array에 저장했을때랑 별 차이없었음. 최대 12개라.

• 4방탐색끝나고 연결안하기 고려 vs 4방탐색마다 연결안하기 고려

  • 2배차이남