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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00

www.acmicpc.net

숫자 카드의 개수가 최대 500,000개이기 때문에 이분 탐색으로 해결해야 한다.

이분 탐색을 직접 구현해줘도 되지만 lower_bound와 upper_bound함수를 이용하여 쉽게 답을 구할 수 있다.

 

 

lower_bound : 찾으려는 값 이상이 처음 나타나는 위치를 반환한다.

upper_bound : 찾으려는 값을 처음으로 초과하는 위치를 반환한다.

 

 

upper_bound 값에서 lower_bound 값을 빼면 찾으려는 값의 개수를 구할 수 있다.

 

 

문제에 나와있는 예시를 이용하면 다음과 같은 숫자카드들을 먼저 정렬시킨다.

6 3 2 10 10 10 -10 -10 7 3

 

그럼 다음과 같이 정렬된다.

-10 -10 2 3 3 6 7 10 10 10

 

 

여기서 3의 개수를 찾기 위해 3의 lower_bound 값은 처음으로 3 이상이 나타나는 3번째 위치이고

upper_bound값은 처음으로 3을 초과하는 값(6)이 나타나는 5번째 위치이다.

 

upper_bound - lower_bound = 5 - 3 = 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int n, m;
int arr[500000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i<n; i++) cin >> arr[i];
 
 
    sort(arr, arr + n);
 
 
    cin >> m;
    
    int x;
    while (m--) {
        cin >> x;
        int cnt = upper_bound(arr, arr + n, x) - lower_bound(arr, arr + n, x);
        cout << cnt << ' ';
    }
 
 
    return 0;
}
Colored by Color Scripter
  

 

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2805. 나무 자르기  (0) 2020.01.21
[BOJ] 1654. 랜선 자르기  (0) 2020.01.20
[BOJ] 5567. 결혼식  (0) 2019.11.13
[BOJ] 7662. 이중 우선순위 큐  (0) 2019.11.13
[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16

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

 

5567번: 결혼식

문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m

www.acmicpc.net

먼저 친구관계를 인접 리스트로 구현해주고 입력받은 값이 상근이의 친구(1번과 친구)인 경우 바로 큐에 넣어주고 체크한다. 그럼 처음 큐의 사이즈는 상근이의 친구들 수만큼이 되므로 ans 변수(초대할 친구 수)에 큐 사이즈를 저장한다

 

 

그리고 상근이의 친구들에 대해서 친구를 조사해준다. 아직 check가 되지 않았다면 ans값\을 증가시킨다. 친구의 친구만 더해주면 되므로 친구의 친구는 큐에 새로 넣지 않는다.

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
#include<iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
vector<int> list[501];
bool check[501];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    queue<int> q;
    
    cin >> n >> m;
 
    int x, y;
    for (int i = 0; i<m; i++) {
        cin >> x >> y;
        list[x].push_back(y);
        list[y].push_back(x);
 
        //상근이의 친구를 큐에 넣는다.
        if (x == 1) {
            q.push(y);
            check[y] = true;
        }
        else if (y == 1) {
            q.push(x);
            check[x] = true;
        }
    }
 
    //현재 큐 사이즈가 상근이의 친구 수
    int ans = q.size();
    check[1] = true;
    
 
    int size;
    while (!q.empty()) {
        x = q.front();
        q.pop();
 
        size = list[x].size();
        for (int k = 0; k < size; k++) {
            y = list[x][k];
            if (check[y]) continue;
 
            ans++;
            check[y] = true;
        }
    }
 
    cout << ans << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1654. 랜선 자르기  (0) 2020.01.20
[BOJ] 10816. 숫자 카드 2  (0) 2020.01.20
[BOJ] 7662. 이중 우선순위 큐  (0) 2019.11.13
[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16
[BOJ] 2146. 다리 만들기  (0) 2019.10.16

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

 

7662번: 이중 우선순위 큐

문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또

www.acmicpc.net

stl에 있는 multiset을 사용하면 자동으로 정렬되기 때문에 쉽게 풀 수 있는 문제다.

set은 중복이 허용되지 않기때문에 multiset을 사용하여야한다.

 

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
#include <iostream>
#include <set>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
 
    int k;
    while (T--) {
        multiset<int> ms;
        cin >> k;
        
        while (k--) {
            char i;
            int num;
            cin >> i >> num;
            
            if (i == 'I') {
                ms.insert(num);
            }
            else if (i == 'D') {
                if (ms.empty()) continue;
 
 
                if (num == 1) {
                    //최댓값 삭제
                    ms.erase(--ms.end());
                }
                else {
                    //최솟값 삭제
                    ms.erase(ms.begin());
                }
            }
 
        }
 
        if (ms.empty()) cout << "EMPTY" << '\n';
        else cout << *(--ms.end()) << ' ' << *ms.begin() << "\n";
    }
    
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 10816. 숫자 카드 2  (0) 2020.01.20
[BOJ] 5567. 결혼식  (0) 2019.11.13
[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16
[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17471. 게리맨더링  (0) 2019.10.16

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

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

이 문제는 최소 신장 트리(MST)를 사용하여서 풀 수 있다. 완전 탐색으로도 그냥 풀 수 있다는데 다음에 풀어봐야겠다.

나는 크루스칼 알고리즘을 사용해서 풀었다.

 

 

1. 먼저 BFS로 각 섬에 번호를 붙인다.

2. 각 섬들 간 만들 수 있는 최단 거리의 직선 다리를 다시 BFS로 만들어 본다.

섬이 4개라고 했을 때, 1에서 2, 1에서 3, 1에서 4, 2에서 3, 2에서 4, 3에서 4로 가는 다리를 만들어주면 된다.

(다리 길이가 2 이상이 아니라면 만들 수 없다)

(직선 다리를 만들기 위해서 각 방향마다 쭉쭉 그 방향으로 이동한다.)

3. 다리를 만들 수 있다면 다리 길이와 함께 연결된 두 섬 번호를 벡터에 넣어준다.

4. 모든 다리를 구했으면 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 만들어준다.

 

 

크루스칼 알고리즘을 간단히 설명하면

간선들을 가중치를 기준으로 오름 차순 정렬한 후에

가중치가 제일 작은 것부터 연결되지 않은 간선들을 순차적으로 선택해나가는 알고리즘이다.

그리고 정점이 n 개라면 간선의 개수는 n-1개이므로 선택한 간선이 n-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
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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m;
int map[10][10];
int island[10][10];
int p[7];
vector<pair<int, pair<int, int>>> vt;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int getParent(int a) {
    if (p[a] == a) return a;
    return p[a] = getParent(p[a]);
}
 
 
void unionSet(int a, int b) {
    int rootA = getParent(a);
    int rootB = getParent(b);
    p[rootA] = rootB;
}
 
 
//u번 섬에서 v번 섬으로 가는 직선 최단 거리를 구한다.
void getMinDist(int u, int v) {
    queue < pair<int, int>> q;
 
    //u번 섬에 있는 칸들을 모두 큐에 넣는다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (island[i][j] == u) {
                q.push(make_pair(i, j));
            }
        }
    }
 
    int mindist = 10;
    int x, y;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            int dist = 0;
 
            //한방향으로 계속 이동
            while (true) {
                //범위를 넘어간 경우
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) break;
                //같은 섬인경우 더 탐색하지 않는다.
                if (island[nx][ny] == u) break;
 
                if (island[nx][ny] == v) {
                    //v번섬인 경우 최소거리와 비교후 더 탐색하지 않는다.
                    if (dist > 1 && mindist > dist) mindist = dist;
                    break;
                }
                else if (island[nx][ny] == 0) {
                    //바다인 경우 거리증가하고 이동
                    dist++;
                    nx += dx[k];
                    ny += dy[k];
                }
                else {
                    //다른 섬인 경우 더 탐색하지 않는다.
                    break;
                }
 
            }
        }
    }
 
    //최소거리가 초기값이 아니라면 벡터에 최소거리와 섬의 번호를 넣는다.
    if (mindist != 10) vt.push_back(make_pair(mindist, make_pair(u, v)));
}
 
 
void bfs(int x, int y, int num) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    island[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (map[nx][ny] == 0) continue;
            if (island[nx][ny] != 0) continue;
 
            q.push(make_pair(nx, ny));
            island[nx][ny] = num;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
 
    //섬에 번호를 붙인다.
    int num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //바다인 경우
            if (map[i][j] == 0) continue;
            //이미 번호를 붙인 경우
            if (island[i][j] != 0) continue;
 
            bfs(i, j, ++num);
        }
    }
 
 
    //위에서 번호를 붙인 num이 섬의 개수
    //각 섬들간의 만들수 있는 다리를 모두 만든다.
    for (int i = 1; i <= num - 1; i++) {
        for (int j = i + 1; j <= num; j++) {
            getMinDist(i, j);
        }
    }
 
    int size = vt.size();
 
    //거리를 기준으로 오름차순 정렬
    sort(vt.begin(), vt.end());
 
    //부모 배열 초기화(처음 부모는 자기 자신)
    for (int i = 1; i <= num; i++) p[i] = i;
 
    int sum = 0;
    int cnt = 0;
    int index = 0;
 
    int u, v, dist;
    //선택한 간선의 개수가 섬의개수 -1이 될때까지 간선을 선택한다.
    while (cnt < num - 1) {
        if (index == size) {
            //모든 섬을 연결하는 것이 불가능하다
            cout << -1 << "\n";
            return 0;
        }
 
        dist = vt[index].first;
        u = vt[index].second.first;
        v = vt[index].second.second;
 
        index++;
        if (getParent(u) == getParent(v)) {
            //이미 연결되어 있다.
            continue;
        }
        else {
            //연결되어 있지 않다면 합친다.
            unionSet(u, v);
 
            //연결된 간선의 수 증가
            cnt++;
 
            //다리 길이에 합쳐준다.
            sum += dist;
        }
    }
 
 
    cout << sum << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 5567. 결혼식  (0) 2019.11.13
[BOJ] 7662. 이중 우선순위 큐  (0) 2019.11.13
[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06

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

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북

www.acmicpc.net

먼저 BFS탐색으로 각 섬에 번호를 붙여준다. 이와 관련된 비슷한 문제는 단지 번호 붙이기 문제를 (풀이) 풀어보면 된다. 

 

 

번호를 붙였으면 바다가 아닌 모든 칸에서 다른 섬으로 가는 최단 거리를 다시 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
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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
 
int n;
int map[100][100];
int island[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
//섬에 번호를 붙인다
void bfs(int x, int y, int num) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    island[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            //바다인 경우
            if (map[nx][ny] == 0) continue;
            //이미 번호를 붙인 경우
            if (island[nx][ny] != 0) continue;
 
            q.push(make_pair(nx, ny));
            island[nx][ny] = num;
        }
    }
}
 
 
//최소 거리를 계산한다.
int bfs2(int x, int y, int now) {
    memset(check, false, sizeof(check));
 
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int dist = 0;
    int mindist = 100000;
    while (!q.empty()) {
        int size = q.size();
 
        while (size--) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                //범위 체크
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                //이동한 곳이 같은 섬인 경우
                if (island[nx][ny] == now) continue;
                //이미 방문한 경우
                if (check[nx][ny]) continue;
 
                //바다인 경우 일단 이동한다.
                if (island[nx][ny] == 0) {
                    q.push(make_pair(nx, ny));
                    check[nx][ny] = true;
                }
                else {
                    //바다도 아니고 현재 섬이 아닌 다른 섬이면 지금까지의 거리를 최소거리와 비교한다.
                    if (mindist > dist) mindist = dist;
                }
 
            }
        }
 
        //한번에 갈 수 있는 탐색이 끝나면 거리 증가
        dist++;
 
    }
 
    return mindist;
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    //연결된 섬들에 번호를 붙인다.
    int num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //이미 번호가 붙은 경우
            if (island[i][j] != 0) continue;
            //바다인 경우
            if (map[i][j] == 0) continue;
 
            bfs(i, j, ++num);
        }
    }
 
 
    int ans = 100000;
    int tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //바다인 경우
            if (map[i][j] == 0) continue;
 
            //(i,j)에서 갈 수 있는 가장 가까운 다른 섬까지의 거리를 tmp에 저장
            tmp = bfs2(i, j, island[i][j]);
            //최솟값과 비교
            if (ans > tmp) ans = tmp;
        }
    }
 
    cout << ans << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7662. 이중 우선순위 큐  (0) 2019.11.13
[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16
[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 6359. 만취한 상범  (0) 2019.09.04

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

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

 

먼저 그래프가 연결된 정점 정보로 주어지므로 vector 배열을 사용해서 인접 리스트를 구현해주었다.

adjlist[x] 에는 x에 연결된 정점들을 push해준다.

 

 

 

인구 차이가 가장 적게 나도록 선거구를 나누기 위해서는

DFS로 각 구역들을 선거구 1에 넣는 경우와 선거구 2에 넣는 경우를 모두 구해서 계산해본다.

선거구에 넣을 때, 나중에 BFS탐색 시 연결되어 있는지 확인하기 위해서 check배열을 추가적으로 사용하였다.

선거구 1에 넣는 경우는 check배열의 값을 true로 선거구 2에 넣는 경우는 check배열의 값을 false로 하였다.

 

 

 

각각의 경우에서 BFS탐색으로 한 선거구에 포함되어 있는 구역이 모두 연결되어 있는지 검사해줘야 하는데, 선거구 1과 선거구 2를 각각 BFS로 검사해줬다.

 

 

 

먼저 선거구 1을 검사할 때는 선거구에 있는 지역 하나를 처음에 큐에 넣고 연결된 구역들을 방문하며 방문 체크를 한다.

이때, check배열의 값이 false인 경우(선거구 2인 경우) 방문하지 못한다. BFS탐색이 끝난 후에 같은 선거구인데 방문하지 않았다면 한 선거구 내에 연결되지 않은 구역이 있다는 뜻이므로 false를 리턴한다.

 

 

 

마찬가지로 선거구 2를 검사할 때에도 check배열의 값이 true인 경우 (선거구 1인 경우)를 방문하지 않고 연결된 정점들을 모두 방문한다. 그리고 선거구 내에 방문하지 않은 구역이 있다면 false를 리턴한다.

 

 

 

 

위의 두 가지 경우에서 모두 false를 리턴하지 않았다면 두 선거구가 모두 각 선거구 내의 구역들이 연결되어 있다는 뜻이므로 true를 리턴하고 인구 차이를 계산한다.

 

 

 

 

/*구역의 수가 최대 10개이고, 각 구역의 인구수가 최대 100명이므로 두 구역의 인구 차이가 최대 1000명을 넘지 않으므로 정답을 저장할 ans변수의 초기값을 1000으로 해두었다 */

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n;
int ans;
 
//인구 수 저장
int arr[11];
 
//인접리스트
vector<int> adjlist[11];
 
//선거구 1
vector<int> vt1;
 
//선거구 2
vector<int> vt2;
 
//선거구 1인 경우 true, 선거구 2인 경우 false
bool check[11];
 
//BFS할때 방문체크 배열
bool visit[11];
 
 
bool bfs() {
    //방문배열 초기화
    for (int i = 0; i <= n; i++) visit[i] = false;
 
    //선거구 1이 모두 연결되어 있는지 검사
    queue<int> q;
    q.push(vt1[0]);
    visit[vt1[0]] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        //현재 구역과 연결된 구역들을 검사한다
        int size = adjlist[x].size();
        for (int k = 0; k < size; k++) {
            int nx = adjlist[x][k];
            //이미 방문한 경우
            if (visit[nx]) continue;
            //선거구 2인 경우
            if (!check[nx]) continue;
 
            visit[nx] = true;
            q.push(nx);
        }
    }
 
    //선거구 1에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
    for (int x : vt1) {
        if (!visit[x]) return false;
    }
 
 
    //방문배열 초기화
    for (int i = 0; i <= n; i++) visit[i] = false;
    
    //선거구 2가 연결되어 있는지 검사
    q.push(vt2[0]);
    visit[vt2[0]] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        int size = adjlist[x].size();
        for (int k = 0; k < size; k++) {
            int nx = adjlist[x][k];
            if (visit[nx]) continue;
            //선거구 1인경우
            if (check[nx]) continue;
 
            visit[nx] = true;
            q.push(nx);
        }
    }
 
    //선거구 2에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
    for (int x : vt2) {
        if (!visit[x]) return false;
    }
 
    //각 선거구가 모두 연결되어 있다면 true를 리턴 
    return true;
}
 
 
void calc() {
    if (bfs()) {//각 선거구가 모두 연결되어 있다면 인구차이를 계산
        int sum = 0;
 
        //선거구 1과 선거구 2의 인구차이를 구한다.
        for (int x : vt1) sum += arr[x];
        for (int x : vt2) sum -= arr[x];
        if (sum < 0) sum = -sum;
 
        //최솟값보다 적다면 최솟값 갱신
        if (ans > sum) ans = sum;
    }
 
 
}
 
 
void solve(int index) {
    if (index > n) {
        //선거구에는 최소 1개의 구역이 포함되어야 한다
        if (vt1.size() == 0 || vt2.size() == 0) return;
        
        //인구차이를 계산
        calc();
        return;
    }
 
    //index구역을 선거구 1에 넣는 경우
    vt1.push_back(index);
    check[index] = true;
    solve(index + 1);
    check[index] = false;
    vt1.pop_back();
 
    //index구역을 선거구 1에 넣는 경우
    vt2.push_back(index);
    solve(index + 1);
    vt2.pop_back();
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    int cnt, x;
    for (int i = 1; i <= n; i++) {
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            cin >> x;
            adjlist[i].push_back(x);
        }
        
    }
 
    ans = 1000;
 
    solve(1);
 
    //ans값이 갱신되지 않았다면 두 선거구로 나눌수없는 경우이다.
    if(ans != 1000) cout << ans << '\n';
    else cout << -1 << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16
[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 1931. 회의실배정  (0) 2019.09.02

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

 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로

www.acmicpc.net

처음에 입력을 받을 때 바이러스를 놓을 수 있는 칸(값이 2인 칸)을 벡터에 모두 넣어놓는다.

그리고 이 칸들 중 m개를 선택하여 바이러스 퍼트리는 경우를 모두 해보고 최소 시간을 구한다.

 

 

m개를 모두 골라줬다면 골라준 자리에 바이러스를 넣고 퍼뜨린다.

바이러스를 퍼트리기 위해서 bfs를 사용하고 시간을 구하기 위해서 큐 사이즈만큼 단계별로 진행하였다.

그리고 각 큐 사이즈만큼 시작할 때마다 시간을 1씩 증가시켜서 시간을 구할 수 있다.

이렇게 하면 나중에 큐가 비었을 때도 한 번 더 1이 더해지므로 처음에 시간을 -1부터 시작하든지 나중에 1을 빼주던지 하면 된다.

 

 

바이러스를 모두 퍼뜨렸다면 퍼지는데 걸리는 시간을 리턴해주면 되는데,

모든 빈칸에 바이러스를 퍼졌는지 먼저 검사해주어야 한다.

빈칸인데 바이러스가 퍼져있지 않다면 문제 조건에 따라 시간 대신에 -1을 리턴한다.

 

 

그리고 시간의 최솟값을 구하기 위해서 먼저 정답을 저장할 ans에다가 -1을 초기값으로 넣어놓고 ans가 -1인 경우와 -1이 아닌경우를 나눠서 최솟값을 구해줬다.

먼저 -1인 경우에는 ans가 초기값이거나 bfs의 결괏값이 -1인 경우이다. 이때는 그냥 새로 bfs 한 결과를 바로 넣어주면 된다. -1이 아닌 경우에는 bfs의 결과가 -1이 아닌 ans보다 작은 값이 어야 ans값으로 새로 갱신된다.

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
int ans;
int map[50][50];
bool check[50][50];
vector<pair<int,int> > vt;
vector<int> virus;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int bfs() {
    queue<pair<int, int> > q;
    memset(check, false, sizeof(check));
 
    int x, y;
    //선택한 바이러스를 놓을 수 있는 칸에 바이러스를 놓는다.
    for (int i = 0; i < m; i++) {
        x = vt[virus[i]].first;
        y = vt[virus[i]].second;
 
        q.push(make_pair(x,y));
        check[x][y] = true;
    }
 
 
    int time = -1;
    while (!q.empty()) {
 
        int size = q.size();
        time++;
 
        while (size--) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
 
                //범위
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                //방문체크
                if (check[nx][ny]) continue;
                //벽인경우
                if (map[nx][ny] == 1) continue;
 
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
 
            }
        }
        
    }
 
    //바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //빈칸인데 바이러스가 퍼져있지 않다
            if (map[i][j] == 0 && !check[i][j]) return -1;
        }
    }
 
    return time;
 
}
 
void select(int index, int cnt) {
    if (cnt == m) {
        int tmp = bfs();
        if (ans == -1) ans = tmp;
        else {
            if (tmp != -1 && ans > tmp) ans = tmp;
        }
 
        return;
    }
    if (index == vt.size()) {
        return;
    }
 
 
    //index번째 바이러스를 놓는 경우
    virus.push_back(index);
    select(index + 1, cnt+1);
    virus.pop_back();
 
    //바이러스를 놓지 않는 경우
    select(index + 1, cnt);
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            //바이러스를 놓을 수 있는 칸이면 벡터에 넣는다.
            if (map[i][j] == 2) vt.push_back(make_pair(i, j));
        }
    }
 
    ans = -1;
 
    select(0, 0);
    
    cout << ans << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 1931. 회의실배정  (0) 2019.09.02
[BOJ] 2217. 로프  (0) 2019.09.02

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

 

6359번: 만취한 상범

문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고

www.acmicpc.net

먼저 상범이는 첫 번째 라운드에서 모든 방의 문을 열고, 그다음 라운드부터는 

k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다.

이런 식으로 n번째 라운드까지 진행한다.

 

문제의 입력으로 테스트 케이스와 함께 n값이 주어진다. n값은 방의 개수이자 라운드 진행 수이다.

 

이 문제는 2번째 라운드에서 2의 배수인 방들은 문이 잠겨져 있고 나머지 방들은 열려있는 상태에서

3번째 라운드를 진행한다.

즉, i번째 라운드의 상태에서 i+1번째 라운드의 상태로 바뀌므로 DP(Dynamic Programming)로 해결할 수 있다.

 

n(5 ≤ n ≤ 100)

n의 범위가 위와 같으므로 n이 100인 경우까지 모두 미리 구해놓으면 된다.

DP 식은 다음과 같이 정의할 수 있다.

 

dp[i][j] = true (i번째라운드의 j번 방이 열려있다)

dp[i][j] = false (i번째라운드의 j번 방이 잠겨져 있다)

 

위의 식을 이용하여 1번째라운드부터 n번째라운드까지 순차적으로 구할 수 있다.

dp배열을 모두 구해놨다면 n이 주어졌을 때, dp[n][i] (1<= i <= n) 중 true인 값들(열려있는 방)의 개수를 구해주면 된다.

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
#include<iostream>
#include <cstring>
using namespace std;
 
bool d[101][101];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    //열리면 true 잠기면 false
    //1번째 라운드에서 모든 방을 연다. (true로 초기화)
    memset(d[1], true, sizeof(d[1]));
    
 
 
    //i번째 라운드에서 j번 방 문을 열거나 잠근다.
    for (int i = 2; i <= 100; i++) {
 
        //이전 방 문의 상태를 복사
        for (int j = 1; j <= 100; j++) {
            d[i][j] = d[i - 1][j];
        }
 
        //i의 배수인 방 문만 열거나 잠근다.
        for (int j = i; j <= 100; j += i) {
            if (d[i - 1][j]) d[i][j] = false;
            else d[i][j] = true;
        }
    }
 
 
    int T;
    cin >> T;
 
    int n;
    while (T--) {
        cin >> n;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            //문이 열려있다
            if (d[n][i]) cnt++;
        }
 
        cout << cnt << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 1931. 회의실배정  (0) 2019.09.02
[BOJ] 2217. 로프  (0) 2019.09.02
[BOJ] 1541. 잃어버린 괄호  (0) 2019.09.02

+ Recent posts

티스토리툴바