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

SW Expert Academy

 

✅ 문제 요약

좌표상에서 core의 위치가 주어졌을 때 코어 연결을 위한 전선의 길이를 출력하라

모든 코어가 연결되지 않을 수 있고 연결된 코어 수가 같을 땐 최소 전선 길이를 출력하라

 

🤔 문제 풀이

생각보다 고려할 것이 많아서 쉽지 않았던 문제였다.

보자마자 완전탐색으로 풀어야겠구나 생각이 들었다.

 

1. 코어의 위치 정보를 저장한다. 저장하기 위한 자료구조로 ArrayList<int[]>를 사용했다.

이때 좌표상에서 가장자리에 위치한 코어는 이미 연결된 코어이며 필요한 전선 길이가 0이므로

리스트에 저장하지 않았다.

for(int i = 0; i<n; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int j = 0; j<n; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
        if(map[i][j] == 1) {
            visit[i][j] = true;
            // 가장자리가 아닌 코어 저장
            if(0<i && i<n-1 && 0<j && j<n-1) {
                core.add(new int[] {i,j});
            }
        }

    }
}

 

2. 완탐시작, 리스트에 담아놓은 각 코어로부터 dx dy 방향벡터를 이용해 상하좌우로 진행하며

필요한 전선을 count 하도록 했다. 전선끼리 겹쳐서는 안되므로 visit 배열로 방문처리도 해주었다.

for(int i = 0; i<4; i++) {
    int curLen = connecting(core.get(count), dx[i], dy[i]);
    // 연결되지 못한 코어인 경우
    if(curLen == 0) {
        solve(count+1, len, connect);
    }
    else {
        solve(count+1, len+curLen, connect+1);
        // 다른 경우 탐색을 위한 연결 정보(visit) 초기화
        initVisit(core.get(count), dx[i], dy[i]);
    }
}

 

2-1. 상하좌우 탐색을 했을 때 만약 다른 코어를 만났거나 다른 코어로부터 이어진 전선을 만난 경우

해당 방향으론 더 이상 진행할 수 없기 때문에 해당 코어의 해당 방향으로는 전선 연결을 진행하지

않고 넘어가도록 했다. 이때 방문처리했던 좌표들을 다시 초기화하기 위해 q(큐)에 담아놓았고

q에서 하나씩 꺼내면서 visit[x][y] = false 작업을 해주었다. 

public static int connecting(int[] pos, int dx, int dy) {
    int x = pos[0]; int y = pos[1];
    int count = 0;
    Queue<int[]> q = new LinkedList<>();

    while(true) {
        int nextx = x + dx;
        int nexty = y + dy;

        // x or y가 벽에 닿을때 까지 진행
        if(nextx < 0 || nextx > n-1 || nexty < 0 || nexty > n-1)
            break;

        // 다른 전선 or 코어에 닿으면 이쪽 방향으론 연결 할 수 없는 것
        // 담아놨던 방문 정보를 전부 초기화하고 0을 리턴한다.
        if(visit[nextx][nexty]) {
            while(!q.isEmpty()) {
                int[] poll = q.poll();
                int vx = poll[0];
                int vy = poll[1];
                visit[vx][vy] = false;
            }
            return 0;
        }
        visit[nextx][nexty] = true;
        q.add(new int[] {nextx,nexty});
        x += dx;
        y += dy;
        count++;
    }

    return count;
}

 

2-2. 상하좌우 탐색을 했을 때 map의 끝까지 진행하며 연결에 성공한 경우

"현재까지 연결된 전선 길이 + 현재 코어에서 연결한 전선 길이" 그리고 "연결된 코어 + 1"을

다음 재귀 파라미터로 넘겨주었다. 현재 코어의 다른 방향 벡터로도 진행해야 하기 때문에

재귀에서 탈출했다면 현재 방향벡터로 방문처리 해준 좌표들을 초기화 해주어야 한다. (initVisit)

public static void initVisit(int[] pos, int dx, int dy) {
    int x = pos[0]; int y = pos[1];

    while(true) {
        int nextx = x+dx;
        int nexty = y+dy;

        // x or y가 벽에 닿을때 까지 진행
        if(nextx < 0 || nextx > n-1 || nexty < 0 || nexty > n-1)
            break;

        visit[nextx][nexty] = false;
        x += dx;
        y += dy;
    }
}

 

3. 만약 입력 받은 코어만큼 탐색을 마쳤다면 maxConnect와 현재 Connect를 비교하여

큰 값으로 갱신해주고 maxConnect와 Connect가 같다면 더 전선 길이 len이 짧은 쪽으로 갱신해주었다.

// 모든 코어에 대해서 탐색을 마쳤다면
if(count == core.size()) {
    // 현재 연결된 개수가 answer보다 많으면
    if(connect > maxConnect) {
        maxConnect = connect;
        minLen = len;
    } // 연결 개수가 같으면
    else if(connect == maxConnect) {
        minLen = Math.min(len, minLen);
    }
    return;
}

 

🚨CODE

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

public class Solution {
	static int[][] map;
	static boolean[][] visit;
	static ArrayList<int[]> core;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n, maxConnect, minLen;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int t = 1; t <= testCase; t++) {
			n = Integer.parseInt(br.readLine());
			map = new int[n][n];
			visit = new boolean[n][n];
			core = new ArrayList<>();
			
			for(int i = 0; i<n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int j = 0; j<n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] == 1) {
						visit[i][j] = true;
						// 가장자리가 아닌 코어 저장
						if(0<i && i<n-1 && 0<j && j<n-1) {
							core.add(new int[] {i,j});
						}
					}
					
				}
			}
			maxConnect = 0;
			minLen = Integer.MAX_VALUE;
			solve(0,0,0);
			
			bw.write(String.format("#%d %d\n", t, minLen));
		}
		
		bw.flush();
	}
	// 탐색한 코어 개수, 전선 길이. 연결된 코어 개수
	public static void solve(int count, int len, int connect) {
		// 모든 코어에 대해서 탐색을 마쳤다면
		if(count == core.size()) {
			// 현재 연결된 개수가 answer보다 많으면
			if(connect > maxConnect) {
				maxConnect = connect;
				minLen = len;
			} // 연결 개수가 같으면
			else if(connect == maxConnect) {
				minLen = Math.min(len, minLen);
			}
			return;
		}
		
		for(int i = 0; i<4; i++) {
			int curLen = connecting(core.get(count), dx[i], dy[i]);
			// 연결되지 못한 코어인 경우
			if(curLen == 0) {
				solve(count+1, len, connect);
			}
			else {
				solve(count+1, len+curLen, connect+1);
				// 다른 경우 탐색을 위한 연결 정보(visit) 초기화
				initVisit(core.get(count), dx[i], dy[i]);
			}
		}
		
	}
	public static int connecting(int[] pos, int dx, int dy) {
		int x = pos[0]; int y = pos[1];
		int count = 0;
		Queue<int[]> q = new LinkedList<>();
		
		while(true) {
			int nextx = x + dx;
			int nexty = y + dy;
			
			// x or y가 벽에 닿을때 까지 진행
			if(nextx < 0 || nextx > n-1 || nexty < 0 || nexty > n-1)
				break;
			
			// 다른 전선 or 코어에 닿으면 이쪽 방향으론 연결 할 수 없는 것
			// 담아놨던 방문 정보를 전부 초기화하고 0을 리턴한다.
			if(visit[nextx][nexty]) {
				while(!q.isEmpty()) {
					int[] poll = q.poll();
					int vx = poll[0];
					int vy = poll[1];
					visit[vx][vy] = false;
				}
				return 0;
			}
			visit[nextx][nexty] = true;
			q.add(new int[] {nextx,nexty});
			x += dx;
			y += dy;
			count++;
		}
		
		return count;
	}
	public static void initVisit(int[] pos, int dx, int dy) {
		int x = pos[0]; int y = pos[1];
		
		while(true) {
			int nextx = x+dx;
			int nexty = y+dy;
			
			// x or y가 벽에 닿을때 까지 진행
			if(nextx < 0 || nextx > n-1 || nexty < 0 || nexty > n-1)
				break;

			visit[nextx][nexty] = false;
			x += dx;
			y += dy;
		}
	}
}