[SWEA 1767] 프로세서 연결하기(Java)
문제 출처 : 링크
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
www.swexpertacademy.com
2차원 배열 안에 설치되어 있는 코어에 전선을 연결시키는 문제다
벽에 붙어있는 코어는 전선을 연결할 수 없고, 나머지 코어를 최대한 많이 활용하면서 최소한의 전선 길이를 출력해야하는 문제다
최소한의 전선 길이라는 말로 BFS로 접근하면 힘들어지고, 코어를 많이 가져가기 위해 DFS 탐색 접근이 편하다
우선 코어에 해당하는 1의 값이 들어오면, 벽에 붙어있지 않은 코어들을 list에 저장했다
그리고 dfs를 통해 해당 코어의 index와 코어의 수 coreCnt, 마지막으로 전선의 길이를 저장할 len을 매개변수로 가져간다.
종료 조건은 index가 리스트의 사이즈만큼 증가했을 때이며, 코어의 수가 가장 많았을 때로 len을 갱신하고 만약 수가 같으면 전선의 수가 가장 작은 것을 저장시키며 갱신시켜 나가면 된다.
해당 코어에서 상,하,좌,우 4방향을 돌면서 전선을 뿌려보고, 만약 벽까지 전선을 놓을 수 있을 때 해당 count를 저장해서 그만큼 map 2차원 배열에 1로 채워준다.
전선을 뿌리는 과정에서 만약 1로 채워진 곳을 만난다면, 설치할 수 없는 상황이므로 count 값을 0으로 초기화하고 while문을 탈출하는 방향으로 해결할 수 있다.
dfs는 count의 수, 즉 전선을 깔았냐 못깔았냐로 조건문을 나누어 진행시킨다.
만약 전선을 깔지 못한 상황에서는 index만 증가시켜주고, 전선을 깐 코어는 index와 coreCnt를 증가시키고, len도 count를 더해서 dfs 탐색을 진행하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Solution_1767_프로세서연결하기_김규석 {
static class Process {
int y;
int x;
Process(int y, int x) {
this.y = y;
this.x = x;
}
}
static int N;
static int[][] map;
static int[] dy = { -1, 1, 0, 0 };
static int[] dx = { 0, 0, -1, 1 };
static ArrayList<Process> list;
static int min;
static int max;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int ts = Integer.parseInt(br.readLine().trim());
for (int t = 1; t <= ts; t++) {
N = Integer.parseInt(br.readLine().trim());
map = new int[N][N];
list = 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) {
if (i - 1 < 0 || j - 1 < 0 || i + 1 >= N || j + 1 >= N)
continue;
list.add(new Process(i, j)); // 벽이 아닌 코어 저장
}
}
}
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
dfs(0,0,0);
System.out.println("#" + t + " " + min);
}
}
public static void dfs(int idx, int coreCnt, int len) {
//종료조건 : 증가되는 인덱스가 list의 사이즈만큼 되었을 때
if(idx == list.size()) {
if(max < coreCnt) { // 코어 개수가 더 많아서 갱신해야할 때
max = coreCnt;
min = len;
}
else if (max == coreCnt) { // 코어 개수가 같아서 길이 비교
if(min > len) min = len;
}
return;
}
int y = list.get(idx).y;
int x = list.get(idx).x;
for (int dir = 0; dir < 4; dir++) {
int count = 0;
int originY = y;
int originX = x;
int ny = y;
int nx = x;
while(true) {
ny += dy[dir];
nx += dx[dir];
if(ny < 0 || nx < 0 || ny>=N || nx>=N) { // 벽을 만날때까지
break;
}
if(map[ny][nx] == 1) { // 전선을 만나면 못가는 곳
count = 0;
break;
}
count++;
}
//len += count;
for (int i = 0; i < count; i++) {
originY += dy[dir];
originX += dx[dir];
map[originY][originX] = 1;
}
if(count == 0) { // 전선을 연결할 수 없는 코어
dfs(idx+1, coreCnt, len);
}
else {
dfs(idx+1, coreCnt+1, len+count);
originY = y;
originX = x;
for (int i = 0; i < count; i++) {
originY += dy[dir];
originX += dx[dir];
map[originY][originX] = 0;
}
//len -= count;
}
}
}
}
|
cs |