1. 특정 거리의 도시 찾기
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 300001
int n, m, k, x;
int i, j;
vector<int> arr[MAX];
vector<int> d(MAX, -1);
void bfs(int start) {
d[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto &i: arr[now]) {
if (d[i] == -1) { //방문 안했으면
d[i] = d[now] + 1;
q.push(i);
}
}
}
}
int main() {
cin >> n >> m >> k >> x;
for (int z = 0; z < n; z++) {
cin >> i >> j;
arr[i].push_back(j);
}
bfs(x);
bool isTrue = false;
for (int z = 1; z <= n; z++) {
if (d[z] == k) {
cout << z << "\n";
isTrue = true;
}
}
if (!isTrue)
cout << -1 << "\n";
return 0;
}
2. 연구소
#include <iostream>
#include <vector>
using namespace std;
#define MAX 11
int arr[MAX][MAX];
int tmp[MAX][MAX];
int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int result = 0;
void virus(int x, int y) { //dfs
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx > n || ny < 0 || ny > m)
continue;
if (tmp[nx][ny] == 0) {
tmp[nx][ny] = 2;
virus(nx, ny);
}
}
}
int getScore() {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tmp[i][j] == 0) {
cnt++;
}
}
}
return cnt;
}
void dfs(int cnt) { //dfs로 벽 설치
if (cnt == 3) {
//바이러스 퍼뜨리기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tmp[i][j] = arr[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tmp[i][j] == 2)
virus(i, j);
}
}
//안전영역 최대인 것으로 교체
result = max(result, getScore());
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
cnt++;
dfs(cnt);
arr[i][j] = 0;
cnt--;
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
dfs(0);
cout << result;
return 0;
}
3. 경쟁적 전염
vector 넣고 for(auto i: virus) 돌려서 계속 런타임 에러 떴다 ..^^~
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 201
int n, k, s, x, y;
int arr[MAX][MAX];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
vector<pair<int, pair<int, int> >> virus;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] != 0)
virus.push_back({arr[i][j], {i, j}});
}
}
cin >> s >> x >> y;
sort(virus.begin(), virus.end());
int cur = 1;
while (cur <= s) {
int size = virus.size();
for (int i = 0; i < size; i++) {
int curVirus = virus[i].first;
int curx = virus[i].second.first;
int cury = virus[i].second.second;
for (int i = 0; i < 4; i++) {
int nx = curx + dx[i];
int ny = cury + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n)
continue;
if (arr[nx][ny] > 0)
continue;
arr[nx][ny] = curVirus;
virus.push_back({curVirus, {nx, ny}});
}
}
if (arr[x - 1][y - 1] > 0)
break;
cur++;
}
cout << arr[x - 1][y - 1];
return 0;
}
4. 연산자 끼워넣기
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
int n, num;
vector<int> v, op; //숫자들, 연산자 수
int minNum = 1000000000, maxNum = -1000000000;
cin >> n;
while (n--) {
cin >> num;
v.push_back(num);
}
for (int i = 0; i < 4; i++) {
cin >> num;
for (int j = 0; j < num; j++) {
op.push_back(i);
}
}
do {
int sum = v[0];
for (int i = 0; i < v.size() - 1; i++) {
switch (op[i]) {
case 0: // +
sum += v[i + 1];
break;
case 1: // -
sum -= v[i + 1];
break;
case 2: // *
sum *= v[i + 1];
break;
case 3: // /
sum /= v[i + 1];
break;
}
}
if (sum < minNum) { //최솟값
minNum = sum;
}
if (sum > maxNum) { //최댓값
maxNum = sum;
}
} while (next_permutation(op.begin(), op.end()));
cout << maxNum << "\n" << minNum;
return 0;
}
'⚖️Algorithm > 📝 이취코' 카테고리의 다른 글
[이취코] 유형별 알고리즘 - 최단 경로(C++) (0) | 2022.11.05 |
---|---|
[이취코] 유형별 알고리즘 - 이진 탐색(C++) (0) | 2022.11.04 |
[이취코] 유형별 알고리즘 - 구현(C++) (0) | 2022.11.03 |
[이취코] 유형별 기출 - 그리디 문제(c++) (0) | 2022.11.02 |
[이취코] 10. 그래프 이론 - C++ (0) | 2022.10.22 |