✅ 문제 요약
좌표상에서 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;
}
}
}
'코딩테스트' 카테고리의 다른 글
[JAVA-D3] SWEA 9280 - 진용이네 주차타워 (0) | 2024.05.03 |
---|---|
[JAVA-D3] SWEA 3499 - 퍼펙트 셔플 (1) | 2024.05.01 |
[JAVA-D3] SWEA 6485 - 삼성시의 버스 노선 (1) | 2024.05.01 |
[JAVA-D3] SWEA 3431 - 준환이의 운동관리 (0) | 2024.05.01 |
[JAVA-D3] SWEA 1221 - GNS (1) | 2024.05.01 |