백준 BOJ 새로 나온 문제들 풀어보기 220904
백준 BOJ 25513번 : 빠른 오름차순 숫자 탐색
문제 난이도 : Gold V
알고리즘 분류 : BFS
주어진 5 x 5 크기의 배열에서, 특정 위치에서 시작하여 1, 2, 3, 4, 5, 6을 순서대로 방문하는 최소 경로의 길이를 구하는 문제이다. (이 때, -1은 지나갈 수 없는 칸이며 만약 순서대로 방문하는 것이 불가능하다면 -1을 출력해야 한다.)
BFS를 반복문으로 여러 번 사용하는 문제이다.
초기 위치에서 cur(1 ~ 6으로 반복문을 돌려준다.)를 방문하는 BFS를 구현하고, 방문이 되었다면 초기 위치를 해당 칸의 위치로 바꿔주고 다음 루프를 돌면 된다.
만약 방문이 불가능하다면 -1을 출력해주고 즉시 종료해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
vector<vector<int>> v(5, vector<int>(5));
for(int i=0; i<5; i++)
for(int j=0; j<5; j++) cin >> v[i][j];
int si, sj; cin >> si >> sj;
int ans = 0;
for(int cur=1; cur<=6; cur++) {
queue<pair<int, int>> q;
q.push({si, sj});
vector<vector<int>> dis(5, vector<int>(5, -1));
dis[si][sj] = 0;
bool check = false;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if(v[x][y] == cur) {
ans += dis[x][y];
si = x, sj = y;
check = true;
break;
}
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
if(dis[nx][ny] != -1 || v[nx][ny] == -1) continue;
dis[nx][ny] = dis[x][y] + 1;
q.push({nx, ny});
}
}
if(!check) {
cout << -1 << "\n";
return 0;
}
}
cout << ans << "\n";
}
백준 BOJ 25512번 : 트리를 간단하게 색칠하는 최소 비용
문제 난이도 : Silver I
알고리즘 분류 : 트리, 그래프 탐색
주어진 트리에 대해 각 노드를 검은색 또는 흰색으로 칠하는 비용이 주어지고, 인접한 노드는 다른 색으로 칠하려고 할 때 모든 노드를 칠하는 최소 비용을 구하는 문제이다.
트리이기 때문에 사이클이 없고, 따라서 하나의 노드의 색을 결정하면 모든 나머지 노드들의 색이 결정된다.
따라서 루트 노드를 검은색으로 칠하는 경우와, 흰색으로 칠하는 경우 두 가지를 구한 뒤 비교해서 최솟값을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N;
vector<vector<int>> adj;
vector<int> v, u;
int a = 0, b = 0;
void f(int x, int pre) {
if(pre == 0) a += v[x];
else a += u[x];
for(int i=0; i<adj[x].size(); i++) {
if(pre == 0) f(adj[x][i], 1);
else f(adj[x][i], 0);
}
}
void g(int x, int pre) {
if(pre == 0) b += v[x];
else b += u[x];
for(int i=0; i<adj[x].size(); i++) {
if(pre == 0) g(adj[x][i], 1);
else g(adj[x][i], 0);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N;
adj.resize(N);
for(int i=0; i<N-1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
}
v.resize(N);
u.resize(N);
for(int i=0; i<N; i++) cin >> v[i] >> u[i];
f(0, 0);
g(0, 1);
cout << min(a, b) << "\n";
}
백준 BOJ 25516번 : 거리가 k이하인 트리 노드에서 사과 수확하기
문제 난이도 : Silver II
알고리즘 분류 : 트리, 그래프 탐색
트리가 주어지고, 루트 노드에서 거리가 k 이하인 노드들에서만 사과를 수확할 때 그 개수를 구하는 문제이다. (각 노드의 사과 개수가 주어진다.)
깊이가 k 이하인 노드를 모두 방문하여 노드의 사과 개수를 답에 더해준 뒤, 답을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M, ans = 0;
vector<vector<int>> adj;
vector<int> v;
void f(int x, int dep) {
ans += v[x];
if(dep == M) return;
for(int i=0; i<adj[x].size(); i++) f(adj[x][i], dep+1);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
adj.resize(N);
for(int i=0; i<N-1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
}
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
f(0, 0);
cout << ans << "\n";
}
백준 BOJ 25511번 : 값이 k인 트리 노드의 깊이
문제 난이도 : Silver II
알고리즘 분류 : 트리, 그래프 탐색
트리에서 각 노드가 가지는 값이 따로 주어질 때, 값 k를 가지는 노드의 깊이를 구하는 문제이다.
루트 노드에서부터 재귀적으로 탐색하다가 노드 값이 k인 노드를 방문했을 때의 깊이를 답으로 저장해준다.
탐색이 끝나고 나서 답을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M;
vector<vector<int>> adj;
vector<int> v;
int ans;
void f(int x, int dep) {
if(v[x] == M) ans = dep;
for(int i=0; i<adj[x].size(); i++) f(adj[x][i], dep+1);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
adj.resize(N);
for(int i=0; i<N-1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
}
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
f(0, 0);
cout << ans << "\n";
}
백준 BOJ 25527번 : Counting Peaks of Infection
문제 난이도 : Bronze III
알고리즘 분류 : 구현
문제 제목 그대로 그래프의 피크의 개수를 구하는 문제이다.
v[i] > v[i-1]이면서 동시에 v[i] < v[i+1]인 i의 개수를 세어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int ans = 0;
for(int i=1; i<N-1; i++)
if(v[i] > v[i-1] && v[i] > v[i+1]) ans++;
cout << ans << "\n";
}
}