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=AWXRJ8EKe48DFAUo



영역의 범위가 주어지지 않지만, 안전한 영역으로 잡아줄 수 있다. k의 상한선이 주어지기 때문에.



그에 맞춰서 map을 잡아주고, 불필요한 탐색을 피하기 위해서 좌표 정보를 벡터에 저장해두고, 그 벡터를 이용해서 필요한 곳만 탐색한다.



구조체에는 활성이 지속되는 시간, 활성 시작 시간, 죽는 시간, 상태를 저장한다.


이 정보를 이용해서 다음과 같은 알고리즘을 구현한다.


1. 활성 상태에 있는 세포를 BFS해준다. 한 칸씩만 움직이기 때문에 새로 큐에 삽입하거나 할 필요가 없다. 사전에 필요한만큼 미리 큐에 넣어두고 돌리면 된다.


2. 활성 시간, 비활성 시간이 된 것들의 상태를 변경해준다.



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
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
struct Info {
    int actTime, deathTime, duration = -1, state = -3; //0 1 -1, -2 비활 활 죽음 방금생김
};// 활성화시작시간, 비활시간, 유지기간,   상태
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
typedef pair<int, int> pii;
 
int  row, col, k;
Info map[701][701];
 
queue<pii> q;
vector<pii> v;
 
vector<pii> pos; //위치정보
 
 
void bfs(int Time) {
    int qs = q.size();
    while (qs--) {
        pii cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            
            //나가는 경우 없음
            //if (vis[nr][nc]) continue;
            if (map[nr][nc].state == 0 || map[nr][nc].state == -1 || map[nr][nc].state == 1) continue;
            if (map[nr][nc].duration == -1 || 
                (map[nr][nc].state == -2 && map[cur.first][cur.second].duration >map[nr][nc].duration)) {
                Info tmp;
                tmp.duration = map[cur.first][cur.second].duration;
                tmp.actTime = Time + map[cur.first][cur.second].duration;
                tmp.deathTime = tmp.actTime + tmp.duration;
                tmp.state = -2; //방금생김
                map[nr][nc] = tmp;
                v.push_back({ nr, nc }); // 나중에 state 바꾸기 위함
                pos.push_back({ nr, nc }); //위치 정보에 추가
            }
            
        }
    }
    for (int i = 0; i < v.size(); i++) { //state 바꾸고 bfs 종료
        map[v[i].first][v[i].second].state = 0;
    }
    v.clear();
}    
 
 
void process() {
 
    for (int  tm = 1 ; tm <= k; tm++) { //i = 시간
        
        for (int i = 0; i < pos.size(); i++) {
            int r = pos[i].first;
            int c = pos[i].second;
            if (map[r][c].state == 1) q.push({ r, c });
        }
        bfs(tm); //활성된애들 bfs
        
        //활성시간, 비활성시간 체크해서 업데이트
        for (int i = 0; i < pos.size(); i++) {
            int r = pos[i].first;
            int c = pos[i].second;
            if (map[r][c].actTime == tm) map[r][c].state = 1;
            if (map[r][c].deathTime == tm) map[r][c].state = -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 >> row >> col >> k;
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                Info tmp;
                cin >> tmp.duration;
                if (tmp.duration == 0) continue;
                tmp.actTime = tmp.duration;
                tmp.deathTime = tmp.actTime + tmp.duration;
                
                pos.push_back({ 350 + i, 350 + j }); //위치 저장
                map[i + 350][j + 350] = tmp;
            }
 
        process();
        int ans = 0;
    
        for (int i = 0; i < pos.size(); i++) {
            int r = pos[i].first;
            int c = pos[i].second;
            if (map[r][c].state == 0 || map[r][c].state == 1) ans++; //죽지 않은 것들
        }
 
        cout << "#" << t << ' ' << ans << '\n';
    
        //map 초기화
        for (int i = 0; i < pos.size(); i++) {
            int r = pos[i].first;
            int c = pos[i].second;
            Info tmp;
            map[r][c] = tmp;
        }
        pos.clear();
    }
 
    return 0;
}
 
cs


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

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

SWEA 5650: 핀볼 게임 (C++)  (0) 2019.10.17
SWEA 1767: 프로세서 연결하기 (C++)  (0) 2019.10.17
SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15

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



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
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
int oprFee[43], n, pay, map[21][21], dis[21][21];
queue<pii> q;
 
 
//큐, dis[][] 초기화
void initVis() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = 0;
 
    while (!q.empty()) q.pop();
}
 
int bfs(pii st, int k) {
    int homeCnt = 0;
    
    q.push(st);
    dis[st.first][st.second]++;
    if (map[st.first][st.second] == 1) homeCnt++;
    
 
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        if (dis[cur.first][cur.second] == k) return homeCnt; //검색 종료
 
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || dis[nr][nc] > 0) continue;
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
            if (map[nr][nc] == 1) homeCnt++;
            
        }
    }
    return -1;
}
 
bool cont() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] == 0 && map[i][j] == 1) return true;
        }
    }
    return false;
}
 
int main(void) {
    setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
 
    //크기별 운용비용 미리 계산
    for (int i = 1; i <= 42; i++)
        oprFee[i] = i * i + (i - 1) * (i - 1);
 
    for (int t = 1; t <= T; t++) {
        int totalHome = 0;
        cin >> n >> pay;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                if (map[i][j] == 1) totalHome++;
            }
 
        int Max = 0; 
        int maxPay = totalHome * pay;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 1; k < 43; k++) {
 
                    int retHome = bfs({ i, j }, k);
 
                    //계산
                    if (retHome * pay - oprFee[k] >= 0)
                        if (retHome > Max) Max = retHome;
 
                    //최대로 벌수있는 돈보다 운용 비용이 더 많이들면 break
                    if (maxPay < oprFee[k]) {
                        initVis();
                        break;
                    }
 
                    initVis();
                }
            }
        }
 
        cout << "#" << t << ' ' << Max << '\n';
    }
 
 
    return 0;
}
 
cs


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

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

SWEA 1767: 프로세서 연결하기 (C++)  (0) 2019.10.17
SWEA 5653:줄기세포배양 (C++)  (0) 2019.10.16
SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15

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



조건대로 시뮬레이션을 해주면 된다.


이동할 때, 이동한 개체와 앞으로 이동해야 하는 개체가 겹치는 처리를 하기 위해서 임시적으로 이차원 배열을 만들어서 이동할 때 사용했다.


이동 결과를 임시 배열에 저장해두고, 여러 개체가 들어있는 좌표를 처리해준 이후에, 원래의 map에 옮겨준다.



낚시왕, 나무재테크 문제와 비슷한 방식이 사용되었다.



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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
const int dr[4] = { -1,1,0,0 };
const int dc[4] = { 0,0,-1,1 };
 
struct Info {
    int num;
    int dir; //상하좌우 1234
};
 
vector<Info> map[101][101];
vector<Info> tmp[101][101]; //이동할 때 사용
int n, Time, k;
 
bool cmp(Info a, Info b) {
    return a.num > b.num;
}
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 >> Time >> k;
        for (int i = 0; i < k; i++) {
            int r, c, cnt, dir;
            cin >> r >> c >> cnt >> dir;
            map[r][c].push_back({ cnt, dir });
        }
 
 
        for (int i = 0; i < Time; i++) {
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //이동
                    if (map[i][j].size() != 0) {
                        Info cur = map[i][j][0];
 
                        int nr = i + dr[cur.dir - 1];
                        int nc = j + dc[cur.dir - 1];
 
                        if (nr == 0) {
                            cur.dir = 2;
                            cur.num /= 2;
                        }
                        else if (nr == n - 1) {
                            cur.dir = 1;
                            cur.num /= 2;
                        }
                        else if (nc == 0) {
                            cur.dir = 4;
                            cur.num /= 2;
                        }
                        else if (nc == n - 1) {
                            cur.dir = 3;
                            cur.num /= 2;
                        }
                        tmp[nr][nc].push_back({ cur.num, cur.dir });
 
                        map[i][j].clear(); //초기화
                    }
 
                }
            }
 
            //tmp에 들어있는 복수개 병합, 방향 설정
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (tmp[i][j].size() >= 2) {
                        sort(tmp[i][j].begin(), tmp[i][j].end(), cmp);
                        //개체수 내림차순
 
                        int Sum = 0;
                        for (int k = 0; k < tmp[i][j].size(); k++)
                            Sum += tmp[i][j][k].num;
 
                        Info merged = { Sum, tmp[i][j][0].dir }; //가장 많이 가진 것의 방향
                        map[i][j].push_back(merged);
                        tmp[i][j].clear(); //초기화
                    }
                    else if (tmp[i][j].size() == 1) {
                        map[i][j].push_back(tmp[i][j][0]);
                        tmp[i][j].clear(); //초기화
                    }
                }
            }
 
        }
 
        int ans = 0;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                if (map[i][j].size() != 0) {
                    ans += map[i][j][0].num;
                    map[i][j].clear(); //초기화
                }
            
        cout << "#" << t << ' ' << ans << '\n';
    }
 
    
    return 0;
}
 
cs


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

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

SWEA 5653:줄기세포배양 (C++)  (0) 2019.10.16
SWEA 2117: 홈 방범 서비스 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 4014: 활주로 건설 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15

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

+ Recent posts

티스토리툴바