문제 URL : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf#none
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제접근법 : 구현 +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
|
//By콩순이냉장고
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n;
int board[12][12];
int visit[12][12];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
vector<pair<int, int>> v;
int minlength;
int maxcore;
void print() {
cout << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{
cout << visit[i][j] << " ";
}
cout << endl;
}
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < n;
}
void init() {
memset(board, 0, sizeof(board));
memset(visit, 0, sizeof(visit));
v.clear();
minlength = 1e8;
maxcore = 0;
}
void input() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin>>board[i][j];
if (i == 0 || j == 0 || i == n - 1 || j == n - 1)
continue;
if (board[i][j] == 1)
v.push_back({ i,j });
}
}
}
bool check(int y, int x,int dir,vector<pair<int,int>> &line) {
int ny = y + dy[dir];
int nx = x + dx[dir];
while (isrange(ny, nx)&&board[ny][nx]==0&&visit[ny][nx]==0) {
line.push_back({ ny,nx });
ny += dy[dir];
nx += dx[dir];
}
return !isrange(ny,nx);
}
void setup(vector<pair<int, int>>& line) {
for (int i = 0; i < line.size(); i++)
visit[line[i].first][line[i].second] = 1;
}
void remove(vector<pair<int, int>>& line) {
for (int i = 0; i < line.size(); i++)
visit[line[i].first][line[i].second] = 0;
}
void dfs(int sum=0,int core=0,int idx=0) {
if (idx >= v.size()) {
if (maxcore < core) {
maxcore = core;
minlength = sum;
}
else if (maxcore == core) {
minlength = min(minlength, sum);
}
return;
}
for (int i = 0; i < 4; i++) {
vector<pair<int, int>> line;
if (check(v[idx].first, v[idx].second, i, line)) {
setup(line);
dfs(sum + line.size(), core + 1, idx + 1);//연결됨
remove(line);
}
}
dfs(sum, core, idx + 1);//연결안하기
}
void solve() {
dfs();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
for(int i=1;i<=test;i++){
init();
input();
solve();
cout << "#" << i << " " << minlength << endl;
}
}
|
cs |
모르는점 혹은 궁금한점 어떤 질문이든 댓글은 환영입니다.
'SWEA' 카테고리의 다른 글
| [SWEA] 10966 물놀이를 가자 (0) | 2021.06.21 |
|---|---|
| [SWEA] 11545 틱택톰 (0) | 2021.05.25 |
| [SWEA] 1953 탈주범 검거(모의 SW 역량테스트) (0) | 2020.10.02 |
| [SWEA] 5650 핀볼 게임(모의 SW 역량테스트) (0) | 2020.09.30 |
| [SWEA] 1941 등산로 조성(모의 SW 역량테스트) (0) | 2020.09.30 |
