개발/알고리즘
21년 8월 알고리즘 스터디 5주차
라사 RASA
2022. 7. 2. 18:57
17142 번 : 연구소 3
백트래킹으로 활성화 할 바이러스의 조합을 만들었고, 이를 BFS 로 최소 시간을 구하는 방법으로 풀이했다.
#include
#include
#include
#include
using namespace std;
int N, M, cnt_0, ans;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
vector<vector> map;
vector<vector> visited;
vector<pair<int, int="">> virus, active;
void bfs()
{
int y, x, time;
queue<tuple<int, int,="" int="">> q;
int cnt_copy = cnt_0;
if (cnt_0 == 0)
{
ans = 0;
return;
}
visited.assign(N + 2, vector(N + 2, false));
for (int i = 0; i < active.size(); ++i)
{
q.push({ active[i].first, active[i].second, 0 });
visited[active[i].first][active[i].second] = true;
}
while (!q.empty())
{
tie(y, x, time) = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
if (!visited[y + dy[i]][x + dx[i]] && (map[y + dy[i]][x + dx[i]] == 0 || map[y + dy[i]][x + dx[i]] == 2))
{
q.push({ y + dy[i], x + dx[i], time + 1 });
visited[y + dy[i]][x + dx[i]] = true;
if (map[y + dy[i]][x + dx[i]] == 0 && --cnt_copy == 0)
{
while (!q.empty())
q.pop();
ans = (ans < time + 1) ? ans : time + 1;
}
}
}
}
}
void active_virus(int n)
{
if (active.size() == M)
{
bfs();
}
for (int i = n; i < virus.size(); ++i)
{
active.push_back(virus[i]);
active_virus(i + 1);
active.pop_back();
}
}
int main(void)
{
cin >> N >> M;
ans = 2501;
cnt_0 = 0;
visited.assign(N + 2, vector(N + 2, false));
map.assign(N + 2, vector(N + 2, 1));
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
cin >> map[i][j];
if (map[i][j] == 0)
{
++cnt_0;
}
else if (map[i][j] == 2)
{
virus.push_back({ i,j });
}
}
}
active_virus(0);
if (ans == 2501)
cout << "-1\n";
else
cout << ans << '\n';
}
// 시간 적게 쓰인 소스 : https://www.acmicpc.net/source/32833118
// 분석해 볼 소스 : https://www.acmicpc.net/source/32303370</tuple<int,></pair<int,></vector</vector
1495 번 : 기타리스트
DP 를 이용해서 마지막 곡 볼륨의 최댓값을 구했다.
#include
#include
using namespace std;
int N, S, M;
vector vol_diff;
vector<vector> cache;
int dp(int pos, int P)
{
if (pos == N)
return P;
if (cache[pos][P] != -11)
return cache[pos][P];
int max_vol = -1;
if (P + vol_diff[pos] <= M)
max_vol = dp(pos + 1, P + vol_diff[pos]);
if (P - vol_diff[pos] >= 0)
max_vol = ((M - max_vol) < (M - dp(pos + 1, P - vol_diff[pos]))) ? max_vol : dp(pos + 1, P - vol_diff[pos]);
return cache[pos][P] = max_vol;
}
int main(void)
{
cin >> N >> S >> M;
vol_diff.assign(N + 1, 0);
cache.assign(N + 1, vector(M+1, -11));
for (int i = 0; i < N; ++i)
{
cin >> vol_diff[i];
}
cout << dp(0, S) << '\n';
}
// 깔끔하게 구현한 소스 : https://www.acmicpc.net/source/31948482</vector
8980 번 : 택배
거리가 짧은 것부터 고려하면 최대 박스의 수를 구할 수 있을 거라고 생각해서 구현했다. 배송 스케줄에 이동 거리가 짧은 것부터 배치해서 최대 박스의 수를 구하도록 구현했는데, 배송이 겹칠 때 추가로 배송 가능한 상자의 개수를 구하는 알고리즘에 문제가 있어 부분 성공만 받았다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
int N, C, M, ans;
vector<vector<int>> goods;
vector<tuple<int, int, int, int>> info;
void print()
{
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
cout << goods[i][j] << ' ';
}
cout << '\n';
}
}
int main(void)
{
// vol : 그 구간에서 배송 중인 박스의 가능한
int dis, from, to, cnt, vol, tmp;
cin >> N >> C >> M;
ans = 0;
goods.assign(N + 1, vector<int>(N + 1, 0));
while (M--)
{
cin >> from >> to >> cnt;
info.push_back({ to - from, from, to, cnt });
}
sort(info.begin(), info.end());
for (int i = 0; i < info.size(); ++i)
{
print();
if (i == 5)
{
i = 5;
}
tie(dis, from, to, cnt) = info[i];
cout << from << ' ' << to << '\n';
vol = 0;
for (int j = to; j > from; --j)
{
tmp = 0;
for (int k = 1; k <= N; ++k)
{
tmp = (tmp > goods[k][j]) ? tmp : goods[k][j];
}
vol += tmp;
}
vol = C - vol;
if (vol < 0)
vol = 0;
goods[from][to] = (vol < cnt) ? vol : cnt;
ans += goods[from][to];
}
cout << ans << '\n';
}
10164 번 : 격자상의 경로
통과 여부와 좌표 값을 저장하여 DP 로 풀이했다.
#include
#include
using namespace std;
vector<vector> cache;
int N, M, K;
int dp(bool isPass, int coor)
{
if (coor > N * M || (!isPass && K < coor))
return 0;
else if (coor == N * M)
{
if (isPass)
return 1;
else
return 0;
}
int cnt = 0;
if (cache[isPass][coor] != -1)
return cache[isPass][coor];
isPass = isPass || (coor == K);
if (coor % M != 0)
cnt += dp(isPass, coor + 1);
cnt += dp(isPass, coor + M);
return cache[isPass][coor] = cnt;
}
int main(void)
{
cin >> N >> M >> K;
cache.assign(2, vector((N + 1) * (M + 1), -1));
if(K == 0)
cout << dp(true, 1) << '\n';
else
cout << dp(false, 1) << '\n';
}
// 좋은 소스 : https://www.acmicpc.net/source/31397007
// 소스 분석 : https://www.acmicpc.net/source/30952429</vector
1013 번 : Contact
패턴이 성립하는 경우에만 다음 인덱스로 넘어갈 수 있도록 했고, 이를 통해 모든 경우를 확인하도록 구현했다.
#include
#include
#include
using namespace std;
string input;
bool isMatch;
void check(int pos)
{
if (isMatch)
{
return;
}
if (pos == input.size())
{
cout << "YES\n";
isMatch = true;
}
int tmp = pos;
bool isEnd = false;
if (pos < input.size() - 3 && input.substr(pos, 3) == "100")
{
tmp += 3;
while (tmp < input.size())
{
if (input[tmp] == '0')
{
++tmp;
}
else
break;
}
while (tmp < input.size())
{
if (input[tmp] == '1')
{
// 전의 조건을 만족했다면 언제든 새로운 패턴이 나올 수 있음.
if (isEnd)
{
check(tmp);
}
++tmp;
isEnd = true;
}
else
break;
}
if (isEnd)
check(tmp);
}
if (pos < input.size() - 1 && input.substr(pos, 2) == "01")
check(pos+2);
}
int main(void)
{
int n;
cin >> n;
while (n--)
{
cin >> input;
isMatch = false;
check(0);
if (!isMatch)
cout << "NO\n";
}
}
// 좋은 소스 : https://www.acmicpc.net/source/32973010
1600 번 : 말이 되고픈 원숭이
좌표와 점프 횟수를 큐에 push 하도록 구현하여 BFS 로 풀이했다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int K, W, H;
int knight_dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int knight_dy[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
vector<vector<int>> map;
vector<vector<vector<bool>>> visited;
int main(void)
{
int ans = -1;
int y, x, jump, time;
cin >> K >> W >> H;
map.assign(H + 1, vector<int>(W + 1, 1));
visited.assign(H + 1, vector<vector<bool>>(W + 1, vector<bool>(K + 1, false)));
for (int i = 1; i <= H; ++i)
{
for (int j = 1; j <= W; ++j)
{
cin >> map[i][j];
}
}
queue<tuple<int, int, int, int>> q;
q.push({ 1, 1, 0, 0 });
visited[1][1][0] = true;
while (!q.empty())
{
tie(y, x, jump, time) = q.front();
q.pop();
if (y == H && x == W)
{
ans = time;
break;
}
if (jump < K)
{
for (int i = 0; i < 8; ++i)
{
if (y + knight_dy[i] < 1 || y + knight_dy[i] > H || x + knight_dx[i] < 1 || x + knight_dx[i] > W)
{
continue;
}
if (!visited[y + knight_dy[i]][x + knight_dx[i]][jump+1] && map[y + knight_dy[i]][x + knight_dx[i]] != 1)
{
visited[y + knight_dy[i]][x + knight_dx[i]][jump+1] = true;
q.push({ y + knight_dy[i], x + knight_dx[i], jump + 1, time + 1});
}
}
}
for (int i = 0; i < 4; ++i)
{
if (y + dy[i] < 1 || y + dy[i] > H || x + dx[i] < 1 || x + dx[i] > W)
{
continue;
}
if (!visited[y + dy[i]][x + dx[i]][jump] && map[y + dy[i]][x + dx[i]] != 1)
{
visited[y + dy[i]][x + dx[i]][jump] = true;
q.push({ y + dy[i], x + dx[i], jump, time + 1});
}
}
}
cout << ans << '\n';
}
//canJump 라는 boolean 변수로 visited 으로 점프할 수 있는지만 확인했는데, jump 횟수가 적은게 후에 도달할 수도 있으니 jump 가능 여부가 아닌 jump 횟수로 확인했다.
5639 번 : 이진 검색 트리
구조체를 이용하여 노드를 구현했고, 전위 순회 결과를 통해 트리를 구성한 뒤, 이를 통해 후위 순회 결과를 출력했다.
#include
using namespace std;
struct Node
{
int num;
Node* left;
Node* right;
};
Node* push(Node* node, int num)
{
if (node == NULL)
{
node = new Node();
node->num = num;
node->left = NULL;
node->right = NULL;
}
else
{
if (num < node->num)
{
node->left = push(node->left, num);
}
else
{
node->right = push(node->right, num);
}
}
return node;
}
void postorder(Node* node)
{
if (node->left != NULL)
postorder(node->left);
if (node->right != NULL)
postorder(node->right);
cout << node->num << '\n';
}
int main(void)
{
int input;
Node* root = NULL;
while (cin >> input)
{
root = push(root, input);
}
postorder(root);
}
// 좋은 코드 참조 : https://www.acmicpc.net/source/32954636