https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

 

0~ 최대 높이까지 조합으로 뽑아준다.

 

뽑은 row들에 대하여 모든 경우로 A와 B로 바꿔주고 검사하는 작업을 해주면 된다.

 

#include<iostream>
#include<vector>
using namespace std;

int h, w, k, m[14][21], org[14][21], st = 0;

bool used[14], findAns = false;

vector<int> v;

void changeRow(int r, int val) {
    for (int j = 0; j < w; j++)
        m[r][j] = val;
}

void toOrg(int r) {
    for (int j = 0; j < w; j++)
        m[r][j] = org[r][j];
}

void dfs(int cnt) { //순열로
    if (cnt == (int)v.size()) {
        
        //투과율 검사 -> 만족하면 바로종료. 정답은 cnt
        for (int j = 0; j < w; j++) {
            int sameCnt = 0;
            bool contin = false;
            for (int i = 0; i < h-1; i++) {
                if (m[i][j] == m[i + 1][j]) sameCnt++;
                else sameCnt = 0;

                if (sameCnt == k - 1) {
                    contin = true;
                    break;
                }
                
                
            }
            if (!contin) return; //실패지점
            
            else if (contin && j == w - 1) 
                findAns = true; //정답 찾음
        }
        
        return;
    }

        for (int j = 0; j < 2; j++) {
            changeRow(v[cnt], j); //v[cnt]행을 i로 바꾸기
            dfs(cnt + 1);
            if (findAns) return; //정답 나옴
            toOrg(v[cnt]); //v[cnt]행 원상복구
        }
    
}

void pickRow(int cnt, int goal) { //조합
                                  
    if (cnt == goal) {
        
        dfs(0); //무조건 0아니면 1로
        return;
    }

    if (cnt == 0) st = 0;
    for (int i = st; i < h; i++) {
        if (!used[i]) {
            //row[cnt] = i;
            st = i;
            v.push_back(i);
            used[i] = true;
            pickRow(cnt + 1, goal);
            if (findAns) return;
            used[i] = false;
            v.pop_back();
        }
    }
}

void initMap() {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++)
            m[i][j] = org[i][j];
    }
}
int main(void) {

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> h >> w >> k;
        //a면 0, b면 1
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) {
                cin >> m[i][j];
                org[i][j] = m[i][j]; //원래 배열
            }

    
        int ans = 0;
        for (int i = 0; i < h; i++) {
            pickRow(0, i);
            //초기화
            if (findAns) {
                ans = i;
                break;
            }
            initMap();
        }

        cout << "#" << t << ' ' << ans << '\n';
         
        for (int i = 0; i < h; i++) 
            used[i] = false;

        v.clear();

        findAns = false;
        st = 0;
        
    }

    return 0;
}
저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 5650: 핀볼 게임 (C++)  (0) 2019.10.17
SWEA 1767: 프로세서 연결하기 (C++)  (0) 2019.10.17
SWEA 5653:줄기세포배양 (C++)  (0) 2019.10.16
SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf



문제 조건에 따라서 이미 전원이 들어와있는 코어를 제외한 모든 코어를, 모든 경우로 전원을 연결시켜주면서 만족하는 경우를 찾아주면 된다.



다만, DFS를 진행할 때, 어떠 코어에서, 4방향 어디로도 연결할 수 없어도, 전원에 연결하지 않고 다음 코어에 대한 탐색을 이어갈 수 있도록 처리해야한다.


일반적인 백트래킹이나 DFS에 더해서, 어디에도 연결되지 않는 경우 이어서 탐색하도록 구현해주면 된다.



가령 1 2 3 4 의 코어가 있다고 가정하면, 2번이 어디에도 연결될 수 없더라도, 2번을 제외한 1 3 4가 모두 전원이 들어와서, 답안으로 포함되는 경우가 있을 수 있기 때문에 이 부분도 고려해야 한다.




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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
 
int map[13][13], n;
bool con[13];
vector<pii> v;
 
int pwrCnt = 0, st = 0;
 
 
pii makeWire(pii pos, int dir) { //동서남북 0123
    int len = 0;
 
    if (dir == 0) {
        for (int j = pos.second + 1; j < n; j++) {
            if (map[pos.first][j] != 0)
                return {0, 0};
        }
        for (int j = pos.second + 1; j < n; j++) {
            map[pos.first][j] = 1;
            len++;
        }
        
    }
    else if (dir == 1) {
        for (int j = pos.second - 1; j >= 0; j--) {
            if(map[pos.first][j] != 0)
                return { 0, 0 };
        }
        for (int j = pos.second - 1; j >= 0; j--) {
            map[pos.first][j] = 1;
            len++;
        }
    }
    else if (dir == 2) {
        for (int i = pos.first + 1; i < n; i++) {
            if (map[i][pos.second] != 0)
                return { 0, 0 };
        }
        for (int i = pos.first + 1; i < n; i++) {
            map[i][pos.second] = 1;
            len++;
        }
        
    }
    else {
        for (int i = pos.first -1 ; i >= 0; i--) {
            if (map[i][pos.second] != 0)
                return { 0, 0 };
        }
        for (int i = pos.first - 1; i >= 0; i--) {
            map[i][pos.second] = 1;
            len++;
        }
    }
 
    return {1, len};
}
 
void removeWire(pii pos, int dir) {
    if (dir == 0) 
        for (int j = pos.second + 1; j < n; j++)
            map[pos.first][j] = 0;
 
    else if (dir == 1) 
        for (int j = pos.second - 1; j >= 0; j--)
            map[pos.first][j] = 0;
            
    else if (dir == 2) 
        for (int i = pos.first + 1; i < n; i++) 
            map[i][pos.second] = 0;
        
    else     
        for (int i = pos.first - 1; i >= 0; i--) 
            map[i][pos.second] = 0;
            
}
 
int tot = 0;
int Max = 0;
bool neverChosen = true;
vector<int> lenCandi;
void dfs(int k, int conCnt) {
    if (k == (int)v.size()) {
        
        if (Max < conCnt) {
            Max = conCnt;
            lenCandi.clear();
            lenCandi.push_back(tot);
        }
        else if (Max == conCnt) 
            lenCandi.push_back(tot);
        
        return;
    }
 
    //지금까지 연결한것 + 앞으로 연결할 수 있는거 < Max라면 할 필요가없음
    if (conCnt + (v.size() - k) < Max) return;
 
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (con[i]) continue;
        neverChosen = true;
        for (int j = 0; j < 4; j++) {
            pii res = makeWire(v[i], j);
            
            if (res.first == 1) { //연결가능
                neverChosen = false;
                con[i] = true;
            //    printf("%d 연결됨 %d쪽 깊이 %d\n", i, j, k);
                tot += res.second; //길이
                st = i;
                dfs(k + 1, conCnt+1);
                removeWire(v[i], j);
                con[i] = false;
                tot -= res.second;
            }
            
            if (j == 3 && neverChosen) { //4방으로 모두 연결할수 없는 지점
                st = i;
                dfs(k + 1, conCnt);
            }
 
        }
    }
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        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) {
                    if (i == 0 || j == 0)
                        pwrCnt++; //자동 전원 연결 상태
                    else
                        v.push_back({ i, j });
                }
            }
        }
 
        dfs(0, 0);
 
        sort(lenCandi.begin(), lenCandi.end());
        if (lenCandi.size() == 0) lenCandi.push_back(0);
        cout << "#" << t << ' ' << lenCandi[0] << '\n';
        //초기화
        v.clear();
        pwrCnt = 0;
        tot = 0;
        Max = 0;
        lenCandi.clear();
        neverChosen = true;
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2112: 보호 필름 (C++)  (0) 2019.10.17
SWEA 5650: 핀볼 게임 (C++)  (0) 2019.10.17
SWEA 5653:줄기세포배양 (C++)  (0) 2019.10.16
SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&categoryId=AV5-BEE6AK0DFAVl&categoryType=CODE



초반에 정보들만 잘 잡아둔다면 DP를 이용해서 쉽게 해결할 수 있다.



먼저, 모든 사람과 모든 계단까지 소요 시간을 미리 저장해둔다.


다음으로 DFS를 이용해서 모든 경우에 대해서, 모든 사람에게 계단을 할당해준다.



이제 0번 계단에 배정된 사람과, 1번 계단에 배정된 사람이 있다.


각각 벡터에 담아서, 계단에 빠르게 도착하는 사람이 앞으로 오도록 정렬해준다.



생각해보면, 계단을 사용하는 사람이 3명 이하라면 아무도 기다리지 않고, 도착하자마자 바로 계단으로 내려갈 수 있다.


하지만 계단을 이용하는 사람이 3명을 초과한다면, 경우에 따라서 대기를 하는 사람도 발생 할 수 있다.



예를들어 5번째에 도착한 사람이 있다. 그리고 현재 계단에는 3명의 사람이 있다고 쳐보자.


이 사람보다 3칸 앞에 있는 사람을 기다려야 한다면, 3칸 앞에 있는 사람이 탈출하자마자 들어가면 된다.


혹은, 3칸 앞에있는 사람을 기다릴 필요가 없다면, 즉, 자신이 도착하기도 전에 이미 3칸 앞에 있는 사람은 계단 밖으로 빠져나간 이후라면, 바로 계단에 도착하자마자 들어가면 된다.


이것을 DP로 구현해주면 된다.




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
137
138
139
140
141
142
143
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define INF 987654321
 
using namespace std;
typedef pair<int, int> pii;
struct Person {
    int idx;
    int dis0, dis1;
    pii pos;
};
 
int n, map[11][11]; //i번 사람의 j번 계단까지 소요시간
vector<pii> stair; //계단 위치
vector<Person> people;
 
int pickedStair[11]; //i번째 사람이 고른 계단
int Min = INF;
int d[11];
 
bool cmp0(Person a, Person b) {
    return a.dis0 < b.dis0;
}
 
bool cmp1(Person a, Person b) {
    return a.dis1 < b.dis1;
}
void dfs(int k) {
    if (k == (int)people.size()) {
    
        vector<Person> use0, use1; //~번 계단 사용하는 사람들
 
        for (int i = 0; i < k; i++) {
            if (pickedStair[i] == 0) use0.push_back(people[i]);
            else use1.push_back(people[i]);
        }
 
        
        //0번부터
        sort(use0.begin(), use0.end(), cmp0);
        for (int i = 0; i < use0.size(); i++) {
            if (i < 3) //세명 이하라면 입구 도착 시간 + 계단 내려가는 시간
                d[i] = use0[i].dis0 + map[stair[0].first][stair[0].second];
            
            else { 
                //if가 계단 꽉차서 기다려야 하는 경우
                if (use0[i].dis0 < d[i - 3]) d[i] = d[i - 3] + map[stair[0].first][stair[0].second];
                else //도착하자마자 계단에 들어갈 수 있는 경우
                    d[i] = use0[i].dis0 + map[stair[0].first][stair[0].second];
            }
        }
 
        int time0 = d[use0.size() - 1] + 1;
        
        for (int i = 0; i < use0.size(); i++)
            d[i] = 0;
 
 
        //1번
        sort(use1.begin(), use1.end(), cmp1);
 
        for (int i = 0; i < use1.size(); i++) {
            if (i < 3) 
                d[i] = use1[i].dis1 + map[stair[1].first][stair[1].second];
            
            else {
                if (use1[i].dis1 < d[i - 3]) d[i] = d[i - 3] + map[stair[1].first][stair[1].second];
                else
                    d[i] = use1[i].dis1 + map[stair[1].first][stair[1].second];
            }
        }
 
        int time1 = d[use1.size() - 1] + 1; //대기 시간 추가
 
        for (int i = 0; i < use1.size(); i++)
            d[i] = 0;
 
        int tmp = max(time0, time1);
        if (tmp < Min) Min = tmp;
        
        //초기화
        use0.clear();
        use1.clear();
        return;
    }
 
    for (int i = 0; i < 2; i++) {
        pickedStair[k] = i;
        dfs(k + 1);
    }
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> n;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                if (map[i][j] > 1) stair.push_back({ i, j }); //계단 추가
                else if (map[i][j] == 1) {
                    people.push_back({ cnt,0,0, {i, j} }); //사람 추가
                    cnt++;
                }
            }
        }
 
        //모든 사람의 계단까지 이동 시간
        for (int i = 0; i < people.size(); i++) {
            for (int j = 0; j < 2; j++) {
                if (j == 0)
                    people[i].dis0 = abs(people[i].pos.first - stair[j].first) +
                    abs(people[i].pos.second - stair[j].second);
                else
                    people[i].dis1 = abs(people[i].pos.first - stair[j].first) +
                    abs(people[i].pos.second - stair[j].second);
            }
        }
        
    
        dfs(0);
 
        cout << "#" << t << ' ' << Min << '\n';
 
        //초기화
        Min = INF;
        people.clear();
        stair.clear();
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16
SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu



대각선으로 좌표를 이동하도록 DFS를 구현해주면 된다.



그래프 문제를 풀이할 때 접해봤던 유형으로, 노드에서 사용되었던 숫자를 다시 사용하지 않으면서, 출발지점으로 되돌아가는 데에 필요한 이동 횟수를 구해주면 된다.


이 문제에서는 그러한 경우의 최솟값을 구해주면 되겠다.


그리고 사각형을 이루어야 한다는 것을 생각해서 구현해주면 되겟다.


이 부분은 코드의 주석으로 확인할 수 있다.



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
 
#include<iostream>
#include<vector>
using namespace std;
 
typedef pair<int, int> pii;
const int dr[4] = { 1, 1, -1, -1 };
const int dc[4] = { 1, -1, -1, 1 };
int n, map[21][21];
bool vis[21][21], used[101];
 
pii src;
vector<int> arr;
int Max = -1;
void dfs(pii cur, int dir, int cnt) {
 
    if (cur.first == src.first && cur.second == src.second && cnt > 1) { //시작점으로 바로 되돌아가는 경우 방지
        if (Max < cnt) Max = cnt;
        return;
    }
 
 
    for (int i = 0; i < 2; i++) { //그대로 가거나 꺾거나
 
        if (dir + i >= 4) //이 이상 회전하는 것은 사각형이 아니다
            break;
 
        int nr = cur.first + dr[dir + i];
        int nc = cur.second + dc[dir + i];
    
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
 
        if (!vis[nr][nc] && !used[map[nr][nc]]) {
 
            used[map[nr][nc]] = true;
            //arr.push_back(map[nr][nc]);
            dfs({ nr, nc }, dir + i, cnt + 1);
            //arr.pop_back();
            vis[nr][nc] = false;
            used[map[nr][nc]] = false;
 
        }
        else if (nr == src.first && nc == src.second)
            dfs({ nr, nc }, dir + i, cnt + 1);
    }
}
 
int main(void) {
    //    setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        //cout << '\n';
 
        for (int i = 0; i < n - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                src.first = i;
                src.second = j;
 
                used[map[i][j]] = true; // 출발 숫자 사용처리
                //vis[i][j] = true; 시작지점 방문처리 하지 않음 나중에 다시 돌아와야 하니까
 
                //arr.push_back(map[i][j]); //어떤 노드를 방문했는지 디버깅하기 위한 용도 
 
                dfs({ i, j }, 0, 0); //좌표, 방향, 거쳐간 노드수, 방향전환횟수
 
                used[map[i][j]] = false;
                arr.clear();
 
            }
        }
 
        cout << "#" << tc << ' ' << Max << '\n';
        Max = -1;
 
    }
    return 0;
}
 
 
cs



저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo



가능한 구슬 투하 횟수만큼 중복 순열을 이용해서 구슬 투하 위치를 구한다.


구슬 투하 위치가 결정되면, BFS를 이용해서 폭탄들이 터지게 해준다.


이후에 중력에 의해서 공중에 있는 박스들이 내려오게 하는 처리는, 큐를 이용해서 바닥부터 빈 공간을 넣어주고, 이동해야할 블럭을 큐의 가장 상단에 있는 지점으로 결정해주면 된다.



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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
int n, w, h, org[17][17], map[17][17], Min = 987654321;
bool vis[17][17];
struct Info {
    pii pos;
    int dis;
};
 
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
queue<Info> bomb;
 
vector<int> dropCol;
 
queue<pii> emp;
 
bool allZero() {
    
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (map[i][j] != 0) return false;
        }
    }
    return true;
}
void pick(int k) {
    if (k == n) {
 
        for (int i = 0; i < dropCol.size(); i++) {
            int c = dropCol[i];
            for (int r = 0; r < h; r++) {
                //구슬투하하고 터트리고 칸맞추고
                if (map[r][c] == 1 ) {
                    map[r][c] = 0;
                    break;
                }
                else if (map[r][c] > 1) {
                    bomb.push({ { r, c }, map[r][c] });
                    vis[r][c] = true;
 
                    while (!bomb.empty()) {
                        Info cur = bomb.front();
                        bomb.pop();
                        int dis = cur.dis;
                        map[cur.pos.first][cur.pos.second] = 0;
 
                        //4방향
                        for (int j = 1; j < dis; j++) {
                            for (int m = 0; m < 4; m++) {
                                int nr = cur.pos.first + dr[m] * j;
                                int nc = cur.pos.second + dc[m] * j;
                                
                                if (nr < 0 || nc < 0 || nr >= h || nc >= w) continue;
                                if (map[nr][nc] == 0 || vis[nr][nc]) continue;
                                if (map[nr][nc] >= 1) bomb.push({ { nr, nc }, map[nr][nc]});
                                else map[nr][nc] = 0;
                                vis[nr][nc] = true;
                            }
                        }
                        
                    }
 
                    for (int i = 0; i < h; i++)
                        for (int j = 0; j < w; j++)
                            vis[i][j] = false;
 
                    break;
                }
                
            }
            
            if (allZero()) {
                Min = 0;
                return;
            }
            
            //중력 처리
            for (int allCol = 0; allCol < w; allCol++) {
                for (int r = h - 1; r >= 0; r--) {
                    if (map[r][allCol] == 0) {
                        emp.push({ r, allCol });
                    }
                    else {
                        if (emp.empty()) continue;
                        pii dst = emp.front();
                        emp.pop();
                        map[dst.first][dst.second] = map[r][allCol];
                        map[r][allCol] = 0;
                        emp.push({ r, allCol });
                    }
                }
                while (!emp.empty()) emp.pop();
                
            }
            
        }
        
 
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] != 0) cnt++;
                map[i][j] = org[i][j];
            }
        }
        if (Min > cnt) Min = cnt;
    
        return;
    }
 
    if (Min == 0) return;
    for (int i = 0; i < w; i++) {
        dropCol.push_back(i);
        pick(k + 1);
        dropCol.pop_back();
    }
}
 
int main(void) {
    setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        cin >> n >> w >> h;
        for (int i = 0; i < h; i++) 
            for (int j = 0; j < w; j++) {
                cin >> org[i][j];
                map[i][j] = org[i][j];
            }
        
        //cout << '\n';
        //0~w-1까지 수중에 n개 중복 허용하고 고르기 (순서 상관 X)
        pick(0);
        
        cout << "#" << tc << ' ' << Min << '\n';
        Min = 987654321;
 
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE




테스트 케이스 2번의 경우를 잘 처리해야 한다.


그냥 채집할 수 있는 가장 큰 꿀을 그리디하게 채집하게 되면, 7과 5,5 를 비교한다고 했을 때, 


이윤이 5 두개를 채집했을 경우 더 크기 때문에, 결국 모든 경우에 대해서 이윤을 비교하기 위해 완전탐색이 필요함을 알 수 있다.



일단 사람이 1명이라고 생각하고, 조건에 따라 채집할 수 있는 벌꿀의 위치별 최대 이윤을 시작 지점과 함께 벡터에 저장했다.


이후에 그 벡터에서 두 개를 골라서 (두명이 채집하니까) 그 위치가 겹치지 않으면서 이윤의 합이 최대인 경우를 답으로 출력해주면 된다.



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
 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
 
int map[11][11], n, m, c;
 
bool cmp(int a, int b) {
    return a > b;
}
 
struct Info {
    pii pos;
    int pft;
};
 
bool cmpCandi(Info a, Info b) {
    return a.pft > b.pft;
}
 
 
bool vis[11];
vector<int> arr;
 
int tmpMax = -1;
void dfs(int k, int Sum, int bef, vector<int>& tmp) {
    if (Sum >= c || k == m) {
        //최대이윤인지 확인
        
        bool reduce = false;
        if (Sum > c) { //수집 가능한 양을 초과했으면 직전 수집 양을 감소 시켜줘야함
            Sum -= bef;
            reduce = true; //종료 조건에서 arr벡터 pop을 해주면 다른 부분에서 중복 pop이 되기 때문에 이렇게 처리함
        }
 
        int Size = arr.size();
        if (reduce) Size--; //하나 덜 검사하도록 처리
 
        int tmpPft = 0;
        for (int i = 0; i < Size; i++)
            tmpPft = tmpPft + arr[i] * arr[i];
 
        if (tmpMax < tmpPft) tmpMax = tmpPft; //최대 이윤 갱신
        return;
    }
 
 
    for (int i = 0; i < tmp.size(); i++) {
        if (vis[i]) continue;
        vis[i] = true;
        
        arr.push_back(tmp[i]);
        
        dfs(k+1, Sum+tmp[i], tmp[i], tmp);
        vis[i] = false;
        arr.pop_back();
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> m >> c;
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        vector<Info> candi; //시작지점, 가능 꿀
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n-m; j++) {
                //시작점 i행j열
                vector<int> tmp;
                for (int k = j; k < j + m; k++) 
                    tmp.push_back(map[i][k]); //꿀 후보 추가
                
                //최대 이윤내는 꿀 골라서 이윤 계산
 
                tmpMax = -1;
        
                dfs(0, 0, 0, tmp); //인덱스, 합, 이전까지합,
 
                Info tmpInfo;
                tmpInfo.pos = { i, j };
                tmpInfo.pft = tmpMax;
                candi.push_back(tmpInfo); //시작지점, 이익 push
                
                tmp.clear();
            }
        }
 
        sort(candi.begin(), candi.end(), cmpCandi);
 
        int Max = -1;
        for (int i = 0; i < candi.size(); i++) {
            for (int j = i + 1; j < candi.size(); j++) {
                if (candi[i].pos.first == candi[j].pos.first) { //같은 칸에서 두명이 채집한 경우 pass
                    if (candi[j].pos.second <= candi[i].pos.second + m - 1 ||
                        candi[i].pos.second <= candi[j].pos.second + m - 1) continue;
                }
                if (candi[i].pft + candi[j].pft > Max) Max = candi[i].pft + candi[j].pft;
 
            }
        }
 
        printf("#%d %d\n", tc, Max);
        candi.clear();
    }
    
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE



사용할 수 있는 연산자의 개수를 하나씩 감소시켜보면서 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
#include<vector>
#include<iostream>
#include<set>
#include<climits>
using namespace std;
int n;
long long Min = LONG_MAX;
long long Max = LONG_MAX * -1;
vector<int> opr;
vector<int> arr;
 
set<vector<int> > st;
int num[13];
bool used[13];
 
void pick(int k) {
    if (k == n - 1) {
        long long res = num[0];
        for (int i = 0; i < arr.size(); i++) {
            int cmd = arr[i];
 
            if (cmd == 0)
                res += num[i + 1];
            else if (cmd == 1)
                res -= num[i + 1];
            else if (cmd == 2)
                res *= num[i + 1];
            else
                res /= num[i + 1];
        }
 
        if (res < Min) Min = res;
        if (res > Max) Max = res;
        //st.insert(arr);
        return;
    }
    
 
    for (int i = 0; i < 4; i++) {
        if (opr[i] > 0) {
            arr[k] = i;
            opr[i]--;
            pick(k + 1);
            opr[i]++;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
 
        //더하기, 뺴기, 곱하기, 나누기
        for (int i = 0; i < 4; i++) {
            int cnt;
            cin >> cnt;
            
            opr.push_back(cnt);
        }
        for (int i = 0; i < n; i++)
            cin >> num[i];
    
        for (int i = 0; i < n - 1; i++)
            arr.push_back(0);
 
        pick(0);
        
 
        long long dif = Max - Min;
        if (dif < 0) dif *= -1;
        cout << "#" << tc << ' ' << dif << '\n';
 
        Min = LONG_MAX;
        Max = LONG_MAX * -1;
        opr.clear();
        st.clear();
        arr.clear();
    }
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE




연산자의 수가 가령 1,5,0,3


이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다.


이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다.



따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 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
#include<vector>
#include<iostream>
#include<set>
#include<climits>
using namespace std;
int n;
long long Min = LONG_MAX;
long long Max = LONG_MAX * -1;
vector<int> opr;
vector<int> arr;
 
set<vector<int> > st;
int num[13];
bool used[13];
 
 
 
void pick(int k) {
    if (k == n - 1) {
        long long res = num[0];
        for (int i = 0; i < arr.size(); i++) {
            int cmd = arr[i];
 
            if (cmd == 0)
                res += num[i + 1];
            else if (cmd == 1)
                res -= num[i + 1];
            else if (cmd == 2)
                res *= num[i + 1];
            else
                res /= num[i + 1];
        }
 
        if (res < Min) Min = res;
        if (res > Max) Max = res;
        //st.insert(arr);
        return;
    }
    
    for (int i = 0; i < opr.size(); i++) {
        if (!used[i]) {
 
            //arr.push_back(opr[i]);
            arr[k] = opr[i];
            used[i] = true;
            pick(k + 1);
            used[i] = false;
            //arr.pop_back();
        }
    }
}
void process() {
 
    for (set<vector<int> > ::iterator itr = st.begin(); itr != st.end(); itr++) {
        vector<int> cur = *itr;
    /*    long long res = num[0];
        for (int i = 0; i < cur.size(); i++) 
            res = cal(res, cur[i], num[i + 1]);*/
        
        long long res = num[0];
        for (int i = 0; i < cur.size(); i++) {
            int cmd = cur[i];
 
            if (cmd == 0)
                res += num[i + 1];
            else if (cmd == 1)
                res -= num[i + 1];
            else if (cmd == 2)
                res *= num[i + 1];
            else 
                res /= num[i + 1];
        }
 
        if (res < Min) Min = res;
        if (res > Max) Max = res;
    }
 
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
 
        //더하기, 뺴기, 곱하기, 나누기
        for (int i = 0; i < 4; i++) {
            int cnt;
            cin >> cnt;
            while (cnt--) {
                opr.push_back(i);
            }
        }
        for (int i = 0; i < n; i++)
            cin >> num[i];
    
        for (int i = 0; i < n - 1; i++)
            arr.push_back(0);
 
        pick(0);
        //process();
 
        long long dif = Max - Min;
        if (dif < 0) dif *= -1;
        cout << "#" << tc << ' ' << dif << '\n';
 
        Min = LONG_MAX;
        Max = LONG_MAX * -1;
        opr.clear();
        st.clear();
        arr.clear();
    }
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

백준 2251번: 물통 (C++)  (0) 2019.08.31
백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10

https://www.welcomekakao.com/learn/courses/30/lessons/43162


DFS혹은 BFS를 활용해서 연결되어 있는 정점들의 집합의 수가 몇개인지 구해주면 된다.


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
#include <string>
#include <vector>
 
using namespace std;
bool vis[201];
void dfs(int here, vector<vector<int>> &grp) {
    
    vis[here] = true;
    
    for (int i = 0; i < grp[here].size(); i++) {
        if (grp[here][i] == 0 || vis[i]) continue;
        dfs(i, grp);
    }
}
int solution(int n, vector<vector<int>> coms) {
    
    int ans = 0;
    for (int i = 0; i < coms.size(); i++) {
        if (!vis[i]) {
            ans++;
            dfs(i, coms);
        }
    }
    return ans;
 
    return 1;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 베스트앨범 (C++)  (0) 2019.10.30
프로그래머스: 단어 변환 (C++)  (0) 2019.09.29
프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27
프로그래머스: 소수찾기 (C++)  (0) 2019.09.27

https://www.acmicpc.net/problem/11724



DFS를 활용해서 연결 요소의 개수를 파악해준다. 연결된 클러스터의 개수를 파악하는 문제라고 생각하면 된다.


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
#pragma warning(disable :4996)
#include<iostream>
using namespace std;
 
int grp[1001][1001], n, m; //1-indexed
bool vis[1001];
 
void dfs(int cur) {
    for (int i = 1; i <= n; i++) {
        if (grp[cur][i] == 1 && !vis[i]) {
            vis[i] = true;
            dfs(i);
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= m; i++) {
        int src, dst;
        cin >> src >> dst;
        grp[src][dst] = 1;
        grp[dst][src] = 1; //방향이 없으므로
    }
 
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            //printf("%d에서 실행\n", i);
            vis[i] = true;
            dfs(i);
            ret++; //dfs의 실행 횟수가 곧 연결 요소의 수
        }
    }
 
    cout << ret;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1389번: 케빈 베이컨의 6단계 법칙 (C++)  (0) 2019.09.25
백준 2644번: 촌수계산 (C++)  (0) 2019.09.25
백준 11403번: 경로 찾기 (C++)  (0) 2019.09.25
백준 1152번: 단어의 개수 (C++)  (0) 2019.09.20
백준 2193번: 이친수 (C++)  (0) 2019.09.19

+ Recent posts

티스토리툴바