[SWEA] 1767 프로세서 연결하기 (Java)

[1767 프로세서 연결하기]

난이도: SW Test 샘플문제

문제 출처

SW Expert Academy

---

[아이디어]

완전 탐색을 사용하였다.

우선 모든 코어들의 위치를 저장해 놓는 List를 만들고, 벽에 붙어있는 코어를 제외한 모든 코어들을 넣어주었다.

그 후 dfs를 사용하여 코어를 사방탐색하였다.

 

이 때, 코어 연결 상태를 관리하는 것이 중요한데 나는 boolean 이차원 배열을 사용하였다.

해당 방향으로 연결을 하다가 실패하면 연결하던 상태를 지워줘야하는데, 이 방법이 좀 까다로워서 나는 temp라는 boolean 이차원 배열을 새로 만들어 현재 연결 상태를 따로 관리해주었다.

 

실행 시간은 나쁘지 않게 나왔지만 boolean 이차원 배열을 계속해서 생성해줬기 때문에 메모리가 높게 나왔다.

 

추가)

메모리가 너무 높았기 때문에 연결 상태를 갱신하고 되돌리는 코드를 간단하게 바꾸어 메모리를 낮춰주었다.

남은 코어의 개수와 현재까지 연결에 성공한 코어의 개수를 합한 값이 현재 최대 코어 연결 개수보다 작다면 가지치기를 해주는 백트래킹을 추가하여 실행 시간을 더 줄여주었다.

---

[JAVA 코드]

백트래킹과 메모리를 낮춘 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
     
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;
     
    static int T, N, maxCnt, minSum;
    static int [][] map;
    static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    static List<Point> cores = new ArrayList<>(); // core들의 위치
     
    static class Point {
        int r, c;
         
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        T = Integer.parseInt(br.readLine());
        for(int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            map = new int [N][N];
            cores.clear();
             
            for(int r = 0; r < N; r++) {
                tokens = new StringTokenizer(br.readLine());
                for(int c = 0; c < N; c++) {
                    map[r][c] = Integer.parseInt(tokens.nextToken());
                    if(map[r][c] == 1 && r > 0 && r < N - 1 && c > 0 && c < N - 1) { // 벽에 붙어있는 경우는 무시
                        cores.add(new Point(r, c));
                    }
                }
            }
             
            maxCnt = 0;
            minSum = 0;
            dfs(0, 0, 0);
             
            output.append(String.format("#%d %d\n", t, minSum));
        }
        System.out.println(output);
    }
 
    private static void dfs(int idx, int cnt, int sum) {
        // 남은 코어의 수 + 연결한 코어의 수가 최대 연결 코어의 개수보다 작으면 가지치기
        if(cores.size() - idx + cnt < maxCnt) {
            return;
        }
        if(idx == cores.size()) {
            if(cnt > maxCnt) {
                maxCnt = cnt;
                minSum = sum;
            } else if(cnt == maxCnt && sum < minSum) {
                minSum = sum;
            }
            return;
        }
 
        int r = cores.get(idx).r;
        int c = cores.get(idx).c;
         
        for(int dir = 0; dir < 4; dir++) {
            int count = 0; // 현재 코어의 전선 길이
            int nr = r;
            int nc = c;
             
            while(true) {
                nr += dr[dir];
                nc += dc[dir];
                 
                // 범위를 벗어났거나 다른 코어 또는 전선을 만난 경우
                if(nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    break;
                }
                if(map[nr][nc] == 1) {
                    count = 0;
                    break;
                }
                 
                count++;
            }
             
            int tempR = r;
            int tempC = c;
             
            for(int i = 0; i < count; i++) {
                tempR += dr[dir];
                tempC += dc[dir];
                map[tempR][tempC] = 1; // 전선 깔아주기
            }
             
            if(count == 0) {
                // 연결을 성공하지 못한 경우
                dfs(idx + 1, cnt, sum);
            } else {
                // 연결을 성공한 경우
                dfs(idx + 1, cnt + 1, sum + count); 
                 
                // 연결 상태를 이전으로 되돌리기
                tempR = r;
                tempC = c;
                 
                for(int i = 0; i < count; i++) {
                    tempR += dr[dir];
                    tempC += dc[dir];
                    map[tempR][tempC] = 0; // 전선 지우기
                }
            }
        }
    }
}

 

처음 코드 (메모리가 높다)

// 메모리: 57,188 kb
// 실행시간: 228 ms

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

public class Solution {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int T, N, maxCnt, minSum;
	static int [][] map;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	static List<Point> cores = new ArrayList<>(); // core들의 위치
	
	static class Point {
		int r, c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int [N][N];
			cores.clear();
			
			for(int r = 0; r < N; r++) {
				tokens = new StringTokenizer(br.readLine());
				for(int c = 0; c < N; c++) {
					map[r][c] = Integer.parseInt(tokens.nextToken());
					if(map[r][c] == 1 && r > 0 && r < N - 1 && c > 0 && c < N - 1) { // 벽에 붙어있는 경우는 무시
						cores.add(new Point(r, c));
					}
				}
			}
			
			maxCnt = 0;
			minSum = 0;
			dfs(0, 0, 0, new boolean [N][N]);
			
			output.append(String.format("#%d %d\n", t, minSum));
		}
		System.out.println(output);
	}

	private static void dfs(int idx, int cnt, int sum, boolean [][] visited) {
		if(idx == cores.size()) {
			if(cnt > maxCnt) {
				maxCnt = cnt;
				minSum = sum;
			} else if(cnt == maxCnt && sum < minSum) {
				minSum = sum;
			}
			return;
		}
		
		boolean flag = true;
		for(int i = 0; i < 4; i++) {
			// 현재 연결 상태를 복사
			boolean [][] temp = copy(visited);
			// 복사된 연결 상태에 현재 코어를 해당 방향으로 연결 시도
			int s = fill(cores.get(idx).r, cores.get(idx).c, i, temp);
			if(s == -1) {
				// 연결 실패
			} else {
				// 연결에 성공하면 갱신 된 연결 상태를 전달
				dfs(idx + 1, cnt + 1, sum + s, temp);
				flag = false;
			}
		}
		
		// 현재 코어가 한 번도 연결에 성공하지 못한 경우
		if(flag) {
			// 전달 받은 연결 상태를 전달
			dfs(idx + 1, cnt, sum, visited);
		}
	}

	// 연결 상태 복사하기
	private static boolean[][] copy(boolean[][] visited) {
		boolean [][] temp = new boolean [N][N];
		
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				temp[r][c] = visited[r][c];
			}
		}
		
		return temp;
	}

	// 연결 상태 갱신하기
	private static int fill(int r, int c, int i, boolean[][] temp) {
		int nr = r + dr[i];
		int nc = c + dc[i];
		int cnt = 0;
		while(true) {
			// 벽에 닿는 경우 연결 성공
			if(nr == -1 || nc == -1 || nr == N || nc == N) break;
			
			// 다른 코어나 다른 연결 선에 닿은 경우 연결 실패
			if(map[nr][nc] == 1 || temp[nr][nc]) {
				return -1;
			}
			temp[nr][nc] = true;
			cnt++;
			
			nr += dr[i];
			nc += dc[i];
		}
		
		return cnt;
	}

}