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




1. 섬마다 인덱스를 부여한다. (각각의 섬들을 구분한다.)


2. 모든 경우에 다리를 놓아본다.

다리를 놓을 수 있는 조건에 맞춰서(길이 2이상)


3. 당연하게도 모든 섬을 최소의 간선으로 연결하는 경우, 간선의 수는 섬의 수 - 1이다.


하지만 다리마다 비용이 다 다르기 때문에, 많은 다리를 적은 비용을 놓고 연결하는 경우가 있을 것이다.


따라서 찾은 다리의 수가 k개라고 하고, 섬의 개수를 N개라고 한다면,



찾은 다리 k개 중에 (N-1개~K개)를 뽑아보고, 섬의 연결상태를 확인해서 모든 섬을 연결할 수 있는 경우에 답을 업데이트 해준다.




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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include<iostream>
#include<queue>
#define INF 987654321
 
using namespace std;
typedef pair<int, int> pii;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
 
struct Info{
    int isl = -1;
    int val = 0;
};
 
struct Bridge {
    int src, dst, len;
};
 
vector<Bridge> v;
 
Info m[101][101];
int R, C, islCnt = 0;
 
queue<pii> q;
bool vis[101][101];
 
int brg[7][7]; //다리 길이 정보
 
int st = 0;
bool used[40];
int arr[100]; //뽑는다리
int ans = INF;
 
bool vis2[7];
 
int map[7][7];
 
queue<int> q2;
 
void bfs(pii st) { //섬 번호 매기는 용도
    q.push(st);
    vis[st.first][st.second] = true;
    m[st.first][st.second].isl = islCnt;
    while (!q.empty()) {
        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 (nr < 0 || nc < 0 || nr >= R || nc >= C || vis[nr][nc]) continue;
            if (m[nr][nc].val == 0) continue;
            
            q.push({ nr, nc });
            vis[nr][nc] = true;
            m[nr][nc].isl = islCnt;
        }
    }
}
 
void bfsCon(int st) { //다리 골랐을 때 연결 관계 확인
    q2.push(st);
    vis2[st] = true;
    while (!q2.empty()) {
        int cur = q2.front();
        q2.pop();
        for (int i = 0; i < islCnt; i++) {
            if (map[cur][i] == 0) 
                continue;
            if (vis2[i]) 
                continue;
            q2.push(i);
            vis2[i] = true;
            
        }
    }
}
 
void btk(int k, int goal) {
    if (k == goal) {
    
        int len = 0;
        for (int i = 0; i < k; i++) {
            Bridge b = v[arr[i]];
            map[b.src][b.dst] = b.len;
            map[b.dst][b.src] = b.len;
            len += b.len;
        }
 
    
        bool isBreak = false;
        for (int i = 0; i < islCnt; i++) {
            for (int j = 0; j < islCnt; j++) {
                if (i == j) continue;
                if (map[i][j] != 0) {
                    bfsCon(i);
                    isBreak = true;
                    break;
                }
 
            }
            if (isBreak) break; //연결 관계 확인은 딱 한 번만
        }
        
        bool suc = true;
        for (int i = 0; i < islCnt; i++) {
            if (!vis2[i]) //실패
                suc = false;
 
            vis2[i] = false; //초기화
            for (int j = 0; j < islCnt; j++) 
                map[i][j] = 0;
            
        }
 
        if (suc) 
            if (ans > len) ans = len;
            
        return;
    }
 
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            arr[k] = i;
            btk(k + 1, goal);
            used[i] = false;
        }
    }
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    //땅이나오면 이 땅에서 길이 2 이상의 다리로 연결가능한 섬 찾아서
    //그 땅이 속한 섬에서 연결할 수 있는 곳에 추가
    //v[k].pushback n  -> k번 섬에서 n번섬에 갈 수 있다. 길이 몇으로
    
    cin >> R >> C;
    for (int i = 0; i < R; i++) 
        for (int j = 0; j < C; j++) 
            cin >> m[i][j].val;
        
    
 
    //섬 번호 부여
    for (int i = 0; i < R; i++) 
        for (int j = 0; j < C; j++) 
            if (m[i][j].val == 1 && !vis[i][j]) {
                bfs({ i, j });
                islCnt++;
            }
        
    //다리 길이 무한대로 초기화
    for (int i = 0; i < islCnt; i++) 
        for (int j = 0; j < islCnt; j++) 
            brg[i][j] = INF;
        
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (m[i][j].val == 0) continue;
            //바다는 pass
            
            for (int k = 0; k < 4; k++) { //4방향으로 다리 놔보기
                //범위 벗어나면 다른 경우
                // 1이면서 나랑 다른 섬이어야 다리에 추가
 
                for (int p = 1; p < 101; p++) {
                    int nr = i + dr[k] * p;
                    int nc = j + dc[k] * p;
                    if (nr < 0 || nc < 0 || nr >= R || nc >= C || (m[nr][nc].isl == m[i][j].isl)) break;
                    if (m[nr][nc].val == 1 && p <= 2) break; //길이 1 이하인 다리
                    if (m[nr][nc].val == 1 && (m[nr][nc].isl != m[i][j].isl) && p >= 3) {
                        //p-1이 다리길이
                        if (brg[m[nr][nc].isl][m[i][j].isl] > p - 1) {
                            brg[m[nr][nc].isl][m[i][j].isl] = p - 1;
                            brg[m[i][j].isl][m[nr][nc].isl] = p - 1;
                        }
                        break;
                    }
                }
            }
        }
    }
 
    
    for (int i = 0; i < islCnt; i++) 
        for (int j = i; j < islCnt; j++) 
            if (brg[i][j] != INF) 
                v.push_back({ i, j, brg[i][j]}); //다리 정보
    
    for (int i = islCnt - 1; i <= v.size(); i++) //최소 섬개수-1개의 다리로 연결 or 모든 다리 사용
        btk(0, i);
    
 
    if (ans == INF) cout << -1;
    else cout << ans;
 
    return 0;
}
 
cs


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

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

백준 1717번: 집합의 표현(C++)  (0) 2021.10.06
백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

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=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=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE




통로를 통해서 이동을 하는데, 현재의 통로에서 목적지의 통로로 이동할 수 있는지 확인해가며 BFS를 구현해주면 된다.




BFS의 특성상 가까운 지점을 무조건 먼저 방문하게 되므로, 임계 거리를 방문하는 순간 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
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
 
int m[51][51], dis[51][51];
vector<vector<int> > dr = { {0,0,1,-1}, {1,-1}, {0,0}, {0, -1},{1, 0},{1,0}, {-1,0} }; //동서남북
vector<vector<int> > dc = { {1,-1,0,0}, {0,0}, {1,-1}, {1,0}, {0,1}, {0, -1}, {0,-1} };
 
queue<pii> q;
 
int r, c, mr, mc, Time; //m~ 맨홀 위치
int cnt = 0;
 
int findDir(int nr, int nc) {
    if (nr == 0 && nc == 1) return 1;
    else if (nr == 0 && nc == -1) return 2;
    else if (nr == 1 && nc == 0) return 3;
    else return 4;
}
 
bool dirCheck(int srcDir, int desIdx) {
    if (srcDir == 1) { //동쪽으로 이동중인 경우
        if (desIdx == 2 || desIdx == 4 || desIdx == 5) return false;
        else return true;
    }
    else if (srcDir == 2) { //서쪽으로 이동중인 경우
        if (desIdx == 2 || desIdx == 6 || desIdx == 7) return false;
        else return true;
    }
    else if (srcDir == 3) { //남쪽으로 이동중인 경우
        if (desIdx == 3 || desIdx == 5 || desIdx == 6) return false;
        else return true;
    }
    else { //북쪽으로 이동중인 경우
        if (desIdx == 3 || desIdx == 4 || desIdx == 7) return false;
        else return true;
    }
}
 
void bfs(pii st) {
    q.push(st);
    dis[st.first][st.second]++; //시작점 시간 1로
    cnt++;
    
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        if (dis[cur.first][cur.second] >= Time) return; //탈출조건
 
        int deltaIdx = m[cur.first][cur.second]; //1나오면 0으로 써야함(좌표 이동 벡터 인덱스)
        
        for (int i = 0; i < dr[deltaIdx - 1].size(); i++) {
            int nr = cur.first + dr[deltaIdx - 1][i];
            int nc = cur.second + dc[deltaIdx - 1][i];
 
            if (nr < 0 || nc < 0 || nr >= r || nc >= c || dis[nr][nc] >= 1) continue;
            if (m[nr][nc] == 0) continue;
 
            int curDir = findDir(dr[deltaIdx - 1][i], dc[deltaIdx - 1][i]); //어느 방향으로 이동중인지
            
            
            if (!dirCheck(curDir, m[nr][nc])) continue; //이동할 수 없는 방향
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
 
            cnt++;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
 
        cin >> r >> c >> mr >> mc >> Time;
        
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                cin >> m[i][j]; 
        
        bfs({ mr, mc });
        
        printf("#%d %d\n", tc, cnt);
 
        //초기화
        cnt = 0;
        while (!q.empty()) q.pop();
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                dis[i][j] = 0;
    }
    return 0;
}
 
 
cs


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

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

SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 1952: 수영장 (C++)  (0) 2019.10.04

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




문제에서, 행과 열을 기존에 사용하던 방식과 다르게 사용하고 있기 때문에, 기존에 익숙한 방식으로 바꿔주었다.


남쪽으로 갈수록 행이 증가하고, 동쪽으로 가면 열이 증가하는 방식으로.



그리고 2차원 배열 안에 pair 벡터를 담았다.


벡터로 담은 이유는, 특정 지점에서 충전기 여러개의 영향을 받을 수 있기 때문이다.


그리고 벡터를 pair로 받은 이유는 충전세기와 함께 어떤 충전기의 영향을 받는지 확인할 수 있어야, 중복 충전때 충전 값 조절해주는 처리를 할 수 있기 때문이다.


이렇게 틀을 잡아두고, BFS를 이용해서 충전 영역을 map에 포시하였다.




다음으로, 간단한 경우부터 생각해보면


A와 B중 하나만 충전 영역에 위치하고 있다면, 그 위치에서 최대 충전량으로 충전을 하면 된다. 따라서 아까 pair 벡터를 충전량 내림차순으로 정렬해두고 사용한다.


나머지 경우는 A와 B 모두 1개 이상의 충전 영역을 지나고 있는 경우이다.


이 경우에는 모든 경우를 다 조사해서 최대 충전량을 찾아줘야 하기 때문에, 이중 for문을 통해서 최대 충전량을 찾아준다.



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
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
 
int pathA[101], pathB[101];
 
vector<pii> map[11][11];
 
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
struct BC {
    int r, c, range, pwr;
} bc[9];
 
queue<pii> q;
int dis[11][11];
void bfs(BC st, int num) {
    q.push({st.r, st.c});
 
    dis[st.r][st.c]++;
    map[st.r][st.c].push_back({ st.pwr, num});
 
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        if (dis[cur.first][cur.second] >= st.range) continue;
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (dis[nr][nc] >= 0)continue;
            
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
            map[nr][nc].push_back({st.pwr, num});
        }
    }
}
 
bool cmp(pii a, pii b) { //충전량 내림차순 정렬
    return a.first > b.first;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int moves, cnt;
        cin >> moves >> cnt;
        for (int i = 0; i < moves; i++) 
            cin >> pathA[i];
        for (int i = 0; i < moves; i++)
            cin >> pathB[i];
        
        for (int i = 0; i < cnt; i++) {
            cin >> bc[i].c >> bc[i].r >> bc[i].range >> bc[i].pwr;
 
            for (int i = 1; i <= 10; i++)
                for (int j = 1; j <= 10; j++)
                    dis[i][j] = -1;
            bfs(bc[i], i); //배터리 충전 영역 그리기
        }
        
        //충전량 큰 것부터 나오도록 정렬
        for (int i = 1; i <= 10; i++)
            for (int j = 1; j <= 10; j++)
                if (map[i][j].size() > 1)
                    sort(map[i][j].begin(), map[i][j].end(), cmp);
 
        
        int Sum = 0, ar = 1, ac = 1, br = 10, bc = 10; //a의 row, a의 col ...
        for (int i = 0; i <= moves; i++) {
            
            int difA = 0 , difB = 0; //충전량 변수
            
            if (map[ar][ac].size() >= 1 && map[br][bc].size() >= 1) {
                //둘다 1개 이상 선택 가능
                int Max = -1;
                for (int k = 0; k < map[ar][ac].size(); k++) {
                    difA = map[ar][ac][k].first;
                    for (int p = 0; p < map[br][bc].size(); p++) {
                        difB = map[br][bc][p].first;
                        if (map[ar][ac][k].second == map[br][bc][p].second)
                            difB = 0; //a에서 사용한 걸 b에서도 사용하는 경우
                        if (difA + difB > Max) Max = difA + difB;
                    }
                }
                Sum += Max;
            }
            else if (map[ar][ac].size() == 0 && map[br][bc].size() > 0) 
                Sum += map[br][bc][0].first; //B만 충전 영역에 들어간 경우
 
            else if (map[ar][ac].size() > 0 && map[br][bc].size() == 0)
                Sum += map[ar][ac][0].first; //A만 충전 영역에 들어간 경우 
 
            //printf("%d초  A = %d B = %d\n", i, difA, difB);
 
            if (i == moves) break; //n초 이후로는 갱신되지 않도록
 
 
            //위치 이동
            if (pathA[i] == 1)
                ar--;
            else if (pathA[i] == 2)
                ac++;
            else if (pathA[i] == 3)
                ar++;
            else if (pathA[i] == 4)
                ac--;
 
            if (pathB[i] == 1)
                br--;
            else if (pathB[i] == 2)
                bc++;
            else if (pathB[i] == 3)
                br++;
            else if (pathB[i] == 4)
                bc--;
        }
 
        cout << "#" << tc << ' ' << Sum << '\n';
        //map초기화
        for (int i = 1; i <= 10; i++)
            for (int j = 1; j <= 10; j++)
                if (map[i][j].size() != 0)
                    map[i][j].clear();
    }
 
    return 0;
}
 
 
cs


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

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

SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14
SWEA 1953: 탈주범 검거 (C++)  (0) 2019.10.13
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03

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



선거구가 형성될 수 있는 조건은 선거구에 구역이 1개 이상 포함되는 것이다.



따라서 조합을 이용해서, 주어지는 n개의 구역 중에서 1개 이상 뽑는 경우에 대해서 처리해주면 된다.


단, n개를 뽑게 되면, 다른 선거구에 속하는 구역이 0개가 된다는 의미이므로 n개 뽑는 경우는 제외해준다.




구역을 적절하게 뽑았다면 다음과 같은 처리를 해준다.


우선 n <= 10 으로 작기 때문에 2차원 bool 배열에 구역의 연결 관계를 인접행렬로 나타내준다.


그리고 처음에 뽑은 구역들이 선거구를 이룰 수 있는지(모두 연결되어 있는지) BFS를 이용해서 확인해준다.


처음에 뽑은 구역들이 연결되어 있지 않다면, 유효한 경우가 아니기 때문에 그냥 넘어간다.



만약 처음에 뽑은 구역이 모두 연결되어 유효한 선거구를 형성한다면, 뽑히지 않은 구역들이 선거구를 형성할 수 있는지 확인한다.


선택되지 않은 구역들에 대해서 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
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
 
int n, pop[11], tot = 0, Min = 987654321, st = 1;
bool vis[11], map[11][11], used[11];
queue<int> q;
 
int bfs(int st, bool usedCheck) { //true인 경우가 처음 뽑은 구역들 연결 확인하는 경우
    q.push(st);
    vis[st] = true;
    int restSum = pop[st];
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (usedCheck)
                if (!used[i]) continue; //뽑은 곳들에 대해서만 연결 관계 확인
            
            if (!map[cur][i] || vis[i]) continue;
            
            q.push(i);
            vis[i] = true;
            restSum += pop[i];
        }
    }
    return restSum; //선거구 인원 반환
}
 
void process() {
    int pickedSum, restSum;
    
 
    //처음에 뽑은 게 모두 연결되어 있는지 확인
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            pickedSum = bfs(i, true);
            break;
        }
    }
 
    bool firCon = true;
    for (int i = 1; i <= n; i++) {
        if (used[i]) { //뽑은 것중에
            if (!vis[i]) firCon = false; //연결 안 된거 하나라도 있으면 거르기
        }
    }
 
    for (int i = 1; i <= n; i++) //방문 처리 배열 초기화
        vis[i] = false;
 
    if (!firCon) return;
 
 
    for (int i = 1; i <= n; i++) 
        if (used[i]) vis[i] = true; //확정된 선거구 방문처리
    
    for(int i = 1; i <= n; i++) {
        if (!vis[i]) {
            restSum = bfs(i, false); //나머지 선거구 인원 계산 + 연결 관계 확인
            break;
        }
    }
 
    bool allCon = true;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { //선거구 형셩 불가
            allCon = false;
            break;
        }
    }
    
    if(allCon) {
        int dif = abs(tot - restSum - restSum);
        if (Min > dif) Min = dif;
    }
    for (int i = 1; i <= n; i++)
        vis[i] = false;
}
void btk(int cnt) {
    if (cnt >= 1) {
        if (cnt >= 6) return;
        //전부 다 뽑은 경우 제외
        process();
    }
    
    if (cnt == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            btk(cnt + 1);
            used[i] = false;
        }
    }
}
 
int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pop[i];
        tot += pop[i];
    }
 
    for (int i = 1; i <= n; i++) {
        int edgeCnt;
        cin >> edgeCnt;
        while (edgeCnt--) {
            int dst;
            cin >> dst;
            map[dst][i] = true;
            map[i][dst] = true;
        }
    }
 
    btk(0);
 
    if (Min == 987654321) cout << -1;
    else
        cout << Min;
 
    return 0;
}
cs


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

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

백준 1717번: 집합의 표현(C++)  (0) 2021.10.06
백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

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



단어의 철자를 바꿔가면서 목록에 있는 단어들 사이에서 차례로 변화가 일어날 수 있다는 것을 이용해서


인접행렬을 만들어준다.


초기 시작지점을 찾을 때, 단어를 바꾸고 시작하냐, 수정 없이 시작하냐를 따져준다.


목적 단어가 목록에 없으면 BFS를 수행할 필요도 없이 0을 반환해준다.



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
#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
 
int m[51][51], dis[51], st = -1, en = -1;
bool addOne = false;
queue<int> q;
void bfs(vector<string>& grp) {
    q.push(st);
    dis[st]++;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int cur = q.front();
            q.pop();
 
            for (int i = 0; i < grp.size(); i++) {
                if (m[cur][i] == 0 || dis[i] >= 0) continue;
                q.push(i);
                dis[i] = dis[cur] + 1;
                if (i == en) return;
            }
        }
    }
}
int solution(string src, string dst, vector<string> wrds) {
 
    int len = wrds[0].length();
 
    for (int i = 0; i < wrds.size(); i++) {
        dis[i] = -1;
        if (wrds[i] == src) { //시작 단어와 같은 단어가 목록에 존재
            st = i;
            addOne = false; //결과에 1 더해줄 필요가 없음
        }
        if (wrds[i] == dst) en = i;
 
        if (st == -1) { //시작 단어와 같은 단어가 목록에 없는 경우
            int dif = 0;
            for (int k = 0; k < len; k++) {
                if (wrds[i][k] != src[k]) dif++;
                if (dif > 1) break;
            }
            if (dif == 1) {
                st = i;
                addOne = true; //결과에 1을 더해준다. 시작부터 한번 바꾸고 시작했으니까
            }
        }
 
        //단어를 노드로 인접행렬 만들기
        for (int j = i + 1; j < wrds.size(); j++) {
            int dif = 0;
            for (int k = 0; k < len; k++) {
                if (wrds[i][k] != wrds[j][k]) dif++;
                if (dif > 1) break;
            }
            if (dif == 1) { //철자 하나 다를때만 연결
                m[i][j] = 1;
                m[j][i] = 1;
            }
        }
    }
 
    //목표 단어가 목록에 없으면 0 반환
    if (en != -1)
        bfs(wrds);
    else return 0;
 
    if (dis[en] != -1) { //바꿀 수 있으면
        if (!addOne)
            return dis[en];
        else
            return dis[en] + 1;
    }
    else
        return 0;
}
cs


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

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

프로그래머스: 메뉴 리뉴얼 (C++)  (0) 2021.08.22
프로그래머스: 베스트앨범 (C++)  (0) 2019.10.30
프로그래머스: 네트워크 (C++)  (0) 2019.09.28
프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27

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/3055



다음번에 물이 확산할 곳으로는 이동할 수 없다고 했으므로, 물의 확산을 먼저 수행해준다.


그리고 길이 1만큼 이동 가능한 경우를(특정 시점에 들어있는 큐의 크기만큼만) BFS를 수행해서


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
#pragma warning(disable :4996)
#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 R, C;
char m[51][51];
int dis[51][51];
 
pii st;
queue<pii> q;
queue<pii> fldq;
bool fldVis[51][51];
 
void fldbfs() {
    int qs = fldq.size();
    while (qs--) { //한 번의 확산만 일어나도록
        pii cur = fldq.front();
        fldq.pop();
        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 >= R || nc >= C) continue;
            if (fldVis[nr][nc] || m[nr][nc] =='D' || m[nr][nc] == 'X') continue;
            m[nr][nc] = '*';
        }
    }
}
 
void flood() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!fldVis[i][j] && m[i][j] == '*') {
                fldq.push({ i, j }); //확산 지점들 미리 push
                fldVis[i][j] = true;
            }
        }
    }
    fldbfs();
}
void bfs() {
    q.push(st);
    dis[st.first][st.second]++;
 
    while (!q.empty()) {
        int qs = q.size();
        //물이동 먼저 하고, 길이 1만큼 이동하도록
 
        flood();
        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 (nr < 0 || nc < 0 || nr >= R || nc >= C || dis[nr][nc] >= 0)
                    continue;
                
                if (m[nr][nc] == '*' || m[nr][nc] == 'X') continue;
                
                q.push({ nr, nc });
                dis[nr][nc] = dis[cur.first][cur.second] + 1;
                
                if (m[nr][nc] == 'D') {
                    cout << dis[nr][nc];
                    return;
                }
            }
        }
    }
    
    cout << "KAKTUS";
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    //*물, X돌, 비버굴D, 고슴도치S
    
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            dis[i][j] = -1;
            if (m[i][j] == 'S') {
                st.first = i;
                st.second = j;
            }
        }
    }
 
    bfs();
    
    return 0;
}
 
 
cs


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

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

백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26

+ Recent posts

티스토리툴바