문제링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
해결 아이디어
우선 입력을 받을때 코어의 개수를 corenum으로 받는다.
그후 dfs를 돌리는데, count는 지금까지 탐색을 진행한 코어의 개수, done은 전선을 연결한 코어의 개수,
(두개를 따로 둔 이유는, 전선을 연결하지 않은 채 코어를 진행 시킬 수도 있기 때문이다. 이것을 고려 안하면 테스트케이스 50개중 49개만 맞고 1개가 틀리게 된다.)
우선 가장자리에 있는 코어들은 아무것도 안해도 연결된 상태이니 count 와 done을 1 증가시킨 채로 dfs를 진행한다.
그 후, 상 하 좌 우 총 4가지 경우에 대해, 지금 진행중인 코어의 진행방향으로 전선(2) 나 코어(1)이 '존재하지 않는' 경우에만
배열채우기 - dfs - 배열 복구
의 전형적인 dfs를 이용한 백트래킹 알고리즘을 적용시킨다.
그리고 코어에 전선을 안깐 채로 증가시켜야 하는 경우도 있으니까 그 부분을 96번째 줄처럼 , count만 1 증가시키고 done은 증가시키지않은 채로 또 dfs 진행.
이렇게 해서 count가 corenum까지 온 경우, 몇개의 코어에 전선을 연결시켰는지 파악하면서 최솟값 갱신해가면 풀 수 있다.
14~18줄의
for(int i=0; i<N; i++) {
for (int j = 0; j < N; j++) {
if(cell[i][j]==2)
temp++;
}
}
부분을 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
133
134
135
136
|
#include <iostream>
#include <vector>
using namespace std;
int T,N;
int corenum;
int maxdone;
int cell[13][13];
int answer;
int answerarr[100];
void dfs(int count,int done, vector<pair<int,int>> v){
if(count==corenum){
int temp=0;
for(int i=0; i<N; i++) {
for (int j = 0; j < N; j++) {
if(cell[i][j]==2)
temp++;
}
}
answerarr[done] = min(answerarr[done],temp);
return;
}
int y = v[count].first;
int x = v[count].second;
if(y==0 || y==N-1 || x==0 || x==N-1)
dfs(count+1,done+1,v);
else{
//상
bool flag = true;
for(int i=0; i<y;i++){
if(cell[i][x]!=0) {
flag = false;
break;
}
}
if(flag){
for(int i=0; i<y;i++){
cell[i][x]=2;
}
dfs(count+1,done+1,v);
for(int i=0; i<y;i++){
cell[i][x]=0;
}
}
//하
flag=true;
for(int i=y+1;i<N;i++){
if(cell[i][x]!=0) {
flag = false;
break;
}
}
if(flag){
for(int i=y+1;i<N;i++)
cell[i][x]=2;
dfs(count+1,done+1,v);
for(int i=y+1;i<N;i++)
cell[i][x]=0;
}
//좌
flag=true;
for(int i=0; i<x;i++){
if(cell[y][i]!=0){
flag=false;
break;
}
}
if(flag){
for(int i=0; i<x;i++)
cell[y][i]=2;
dfs(count+1,done+1,v);
for(int i=0; i<x;i++)
cell[y][i]=0;
}
//우
flag=true;
for(int i=x+1; i<N;i++){
if(cell[y][i]!=0){
flag=false;
break;
}
}
if(flag){
for(int i=x+1; i<N;i++)
cell[y][i]=2;
dfs(count+1,done+1,v);
for(int i=x+1; i<N;i++)
cell[y][i]=0;
}
dfs(count+1,done,v);
}
}
int main(void){
cin>>T;
for(int casenum=1; casenum<=T; casenum++){
cin>>N;
vector<pair<int,int>> core;
corenum=0;
maxdone=0;
answer=200;
for(int i=0; i<100; i++)
answerarr[i]=100;
for(int i=0;i<N;i++)
for(int j=0 ; j<N; j++)
cell[i][j]=0;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin>>cell[i][j];
if(cell[i][j]==1){
corenum++;
core.push_back({i,j});
}
}
}
dfs(0,0,core);
for(int i=corenum; i>0; i--){
if(answerarr[i]!=100){
answer = answerarr[i];
break;
}
}
cout<<"#"<<casenum<<" "<<answer<<"\n";
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|