Problem
Problem URL : 프로세서 연결하기
[1] Answer Code (18. 10. 10)
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int ans_core;
int ans_line;
int n;
int map[13][13];
struct Node{
int x;
int y;
Node(int _x, int _y): x(_x), y(_y) {};
};
vector<Node> core_v; // vector list of core's
bool isEdge(int x, int y){
if( (x == 0 || x == n-1) || ( y == 0 || y == n-1 ))
return true;
else
return false;
}
bool isCore(int idx, int dir_idx){
int x = core_v[idx].x;
int y = core_v[idx].y;
while (1) {
if( isEdge(x, y))
break;
x += dx[dir_idx];
y += dy[dir_idx];
if(map[x][y])
return true;
}
return false;
}
int fillLine(int idx, int dir_idx, int value){
int x = core_v[idx].x;
int y = core_v[idx].y;
int line_cnt = 0;
while (1) {
x += dx[dir_idx];
y += dy[dir_idx];
if( x < 0 || x >= n || y < 0 || y >= n )
break;
map[x][y] = value;
line_cnt++;
}
return line_cnt;
}
void dfs(int idx, int core_cnt, int line_cnt){
if(idx == core_v.size()){
if(ans_core < core_cnt){
ans_core = core_cnt;
ans_line = line_cnt;
}
else if( ans_core == core_cnt){
ans_line = ans_line < line_cnt ? ans_line : line_cnt;
}
return;
}
if( isEdge(core_v[idx].x, core_v[idx].y) ){
dfs(idx+1,core_cnt+1,line_cnt);
}
else{
for(int i=0; i<4; i++){ // 4방향 체크
if(! isCore(idx, i)){
int add_line = fillLine(idx,i,1);
dfs(idx+1, core_cnt + 1, line_cnt + add_line);
fillLine(idx,i,0);
}
}
/*
설치하지 않고 Pass
00000
01110
01110
01110
00000
이런 경우에 가운데 있는 코어는 Pass해야한다.
*/
dfs(idx+1,core_cnt,line_cnt);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
for(int tc=1; tc<=TC; tc++){
memset(map,-1,sizeof(map));
core_v.clear();
ans_core = -1;
ans_line = 2e9;
cin >> n;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++){
cin >> map[i][j];
if(map[i][j] == 1)
core_v.push_back(Node(i,j));
}
}
dfs(0,0,0);
cout << "#" << tc << " " << ans_line << endl;
}
return 0;
}
Review
- 생각보다 오래걸렸다.
[2] Answer Code (18. 05. 08)
#include <iostream>
#include <vector>
#include <cstring>
#define P pair<int,int>
using namespace std;
int n,map[12][12];
int num,cnt,size;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int draw(int x, int y, int dir, bool chk){
int cnt = 0;
int _value = chk;
while (1) {
x += dx[dir];
y += dy[dir];
cnt ++;
map[x][y] = _value;
if( x == 0 || x == n-1 || y == 0 || y == n-1 )
break;
}
return cnt;
}
void dfs(vector<P> &v, int idx, int _num, int _cnt){
if( idx >= size ){
if( num < _num ){ // 많은 Core가 우선
num = _num;
cnt = _cnt;
}
else if( num == _num && cnt > _cnt) // Core 수는 같고 cnt값이 작을 때
cnt = _cnt;
}
else {
int x = v[idx].first;
int y = v[idx].second;
if( x == 0 || x == n-1 || y == 0 || y == n-1) // 가장 자리는 그냥 idx와 처리한 Core수만 증가
dfs(v,idx+1,_num+1, _cnt);
else{
for(int i=0; i<4; i++){
x = v[idx].first;
y = v[idx].second;
while (1) {
x += dx[i];
y += dy[i];
// 중지 조건이
// 1. map[x][y] == 1이면 전선을 못 놓는다.
// 2. 가장자리까지 왔다.
if( map[x][y] == 1 || x == 0 || x == n-1 || y == 0 || y == n-1){
break;
}
} // End of While
// 1번 조건으로인해 중간에 끊기면 조건을 위배하므로 false
if( map[x][y] == 0 && (x == 0 || x == n-1 || y == 0 || y == n-1 )){
// Draw
int draw_cnt = draw(v[idx].first, v[idx].second, i, true);
dfs(v,idx+1, _num+1, _cnt+draw_cnt);
// Cancle Draw
draw(v[idx].first, v[idx].second, i, false);
}
else
continue;
}
}
// 0 1 0
// 1 1 1
// 0 1 0
// 위 와 같은 구조일 때 (1,1)은
// idx값만 넘겨야 하기 때문에
dfs(v,idx+1,_num,_cnt);
}
}
int main(){
int tc;
cin >> tc;
for(int st=1; st<=tc; st++){
num = 0;
cnt = 2e9;
memset(map, 0, sizeof(map));
cin >> n;
vector<P> v;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int tmp;
scanf("%d",&tmp);
if(tmp){
map[i][j] = tmp;
v.push_back({i,j});
}
}
}
size = (int)v.size();
dfs(v,0,0,0);
printf("#%d %d\n",st,cnt);
}
return 0;
}
Review
-
어떻게 접근해야할 지 떠오르지 않아 답을 보았다.
-
이 문제를 통해서 배운점 4가지
시간 복잡도 / 문제접근법 / draw 함수에서 T/F로 채우기 / vector 넘기기 /DFS 시간복잡도
[3] Wrong Code (18. 05. 07)
#include <iostream>
#include <vector>
#include <cstring>
#define P pair<int,int>
using namespace std;
int n,map[12][12];
int num,cnt,size;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int draw(int x, int y, int dir, bool chk){
int cnt = 0;
int _value = chk;
while (1) {
x += dx[dir];
y += dy[dir];
cnt ++;
map[x][y] = _value;
if( x == 0 || x == n-1 || y == 0 || y == n-1 )
break;
}
return cnt;
}
void dfs(vector<P> &v, int idx, int _num, int _cnt){
if( idx >= size ){
if( num <= _num ){ // 많은 Core가 우선
if( cnt > _cnt){ // 그 중 cnt 작은 값
num = _num;
cnt = _cnt;
}
else if( num == _num && cnt > _cnt) // Core 수는 같고 cnt값이 작을 때
cnt = _cnt;
}
}
else {
int x = v[idx].first;
int y = v[idx].second;
if( x == 0 || x == n-1 || y == 0 || y == n-1) // 가장 자리는 그냥 idx와 처리한 Core수만 증가
dfs(v,idx+1,_num+1, _cnt);
else{
for(int i=0; i<4; i++){
x = v[idx].first;
y = v[idx].second;
while (1) {
x += dx[i];
y += dy[i];
// 중지 조건이
// 1. map[x][y] == 1이면 전선을 못 놓는다.
// 2. 가장자리까지 왔다.
if( map[x][y] == 1 || x == 0 || x == n-1 || y == 0 || y == n-1){
break;
}
} // End of While
// 1번 조건으로인해 중간에 끊기면 조건을 위배하므로 false
if( map[x][y] == 0 && (x == 0 || x == n-1 || y == 0 || y == n-1 )){
// Draw
int draw_cnt = draw(v[idx].first, v[idx].second, i, true);
dfs(v,idx+1, _num+1, _cnt+draw_cnt);
// Cancle Draw
draw(v[idx].first, v[idx].second, i, false);
}
else
continue;
}
}
// 0 1 0
// 1 1 1
// 0 1 0
// 위 와 같은 구조일 때 (1,1)은
// idx값만 넘겨야 하기 때문에
dfs(v,idx+1,_num,_cnt);
}
}
int main(){
int tc;
cin >> tc;
for(int st=1; st<=tc; st++){
num = 0;
cnt = 2e9;
memset(map, 0, sizeof(map));
cin >> n;
vector<P> v;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int tmp;
scanf("%d",&tmp);
if(tmp){
map[i][j] = tmp;
v.push_back({i,j});
}
}
}
size = (int)v.size();
dfs(v,0,0,0);
printf("#%d %d\n",st,cnt);
}
return 0;
}
Review
-
50개 중 41개가 맞는다.
-
어디가 틀린걸까? 모르겠어서 SWEA 사이트에 질문을 올렸다.
-
이유를 찾았다.
[ if( cnt > _cnt){ // 그 중 cnt 작은 값 ]
이 부분이 잘못되었다. num값이 크면 우선순위가 높기 때문에 무조건 초기화를 해줘야한다.