백준 BOJ 3264번 : ONE
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색
트리 그래프와 출발점이 주어질 때, 출발점에서 모든 노드를 방문하는 최단 경로의 길이를 구하는 문제이다.
사이클이 존재하지 않으므로, 어떤 말단 노드로 들어가면 다시 되돌아와야 한다.
되돌아올 필요가 없는 경우는 해당 노드들을 마지막으로 방문하는 경우이다.
최단 경로는 다시 되돌아오는 경로가 최대한 긴 경로이므로, 출발 노드에서 가장 먼 노드의 거리를 구해서 모든 노드의 합의 2배에서 빼주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> dis;
int Max = 0;
void f(int x) {
Max = max(Max, dis[x]);
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i].first;
if(dis[y] != -1) continue;
dis[y] = dis[x] + adj[x][i].second;
f(y);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
int sum = 0;
adj.resize(N+1);
for(int i=0; i<N-1; i++) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
sum += c;
}
dis.resize(N+1, -1);
dis[M] = 0;
f(M);
int ans = sum*2 - Max;
cout << ans << "\n";
}
백준 BOJ 18243번 : Small World Network
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색
그래프가 주어질 때 두 노드 사이의 거리가 6보다 큰 그래프인지를 판별하는 문제이다.
기본적으로는 모든 노드로부터 BFS를 해준 뒤 거리가 6보다 큰 경우가 있으면 Big World!를 출력해주면 된다.
그러나 그래프가 두 개 이상의 덩어리로 경우도 있으므로 예외 처리 등이 필요하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> adj(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
bool check = true;
for(int i=1; i<=N; i++) {
vector<int> dis(N+1, -1);
dis[i] = 0;
queue<int> q;
q.push(i);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int j=0; j<adj[x].size(); j++) {
int y = adj[x][j];
if(dis[y] != -1) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
for(int j=1; j<=N; j++)
if(dis[j] > 6 || dis[j] == -1) check = false;
}
if(check) cout << "Small World!\n";
else cout << "Big World!\n";
}
백준 BOJ 17040번 : The Great Revegetation (Bronze)
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색, 그리디
정점이 N개이고 간선이 M개인 그래프가 주어질 때, 한 정점과 직접적으로 연결된 다른 정점의 번호가 다르도록 1~4 사이의 번호를 매기고 그 중 사전순으로 가장 작은 답을 구하는 문제이다.
브루트포스로 인접한 노드들의 색 중에서 가능한 가장 작은 번호를 매겨주면 된다.
탐색 방법은 다양한 방법이 있겠지만 나는 adj 벡터에 넣어주고, 1~4를 체크할 bool 벡터를 이용해 브루트포스로 체크해준 뒤 체크 안 된 번호를 칠하고 break 해주는 식으로 구현했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> adj(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> v(N+1);
v[1] = 1;
for(int i=2; i<=N; i++) {
vector<bool> u(5);
for(int j=0; j<adj[i].size(); j++) {
u[v[adj[i][j]]] = true;
}
for(int j=1; j<=4; j++)
if(!u[j]) {
v[i] = j;
break;
}
}
for(int i=1; i<=N; i++) cout << v[i];
cout << "\n";
}
백준 BOJ 16956번 : 늑대와 양
문제 난이도 : Silver III
알고리즘 분류 : 그래프 이론, 애드 혹, 구성적
늑대와 양이 N x M 배열에 주어질 때, 벽을 쳐서 늑대가 양에게 접근하지 못하게 할 수 있는지 여부를 구하고, 그럴 수 있다면 벽이 쳐 진 예시 배열을 하나 구하는 문제이다.
당연히 양과 늑대가 상하좌우에 바로 인접해있지 않다면 벽을 쳐서 분리할 수 있다.
따라서 바로 옆 칸에 인접하는지 검사를 해주고, 그렇지 않다면 각 양의 상하좌우에 모두 벽을 쳐서 양을 보호할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<char>> v(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
bool check = true;
for(int i=0; i<N; i++)
for(int j=0; j<M-1; j++) {
if(v[i][j] == 'S' && v[i][j+1] == 'W') check = false;
if(v[i][j] == 'W' && v[i][j+1] == 'S') check = false;
}
for(int i=0; i<M; i++)
for(int j=0; j<N-1; j++) {
if(v[j][i] == 'S' && v[j+1][i] == 'W') check = false;
if(v[j][i] == 'W' && v[j+1][i] == 'S') check = false;
}
if(!check) {
cout << 0 << "\n";
return 0;
}
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(v[i][j] != 'S') continue;
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};
for(int k=0; k<4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
if(v[ni][nj] != '.') continue;
v[ni][nj] = 'D';
}
}
cout << 1 << "\n";
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) cout << v[i][j];
cout << "\n";
}
}
백준 BOJ 22035번 : Bus Lines
문제 난이도 : Silver IV
알고리즘 분류 : 그래프 이론, 구성적
정점이 N개이고, 간선이 M개인 그래프에 대해 connected 그래프이며 모든 간선의 양 끝 노드의 합이 다른 그래프를 구하는 문제이다.
먼저 최소 간선으로 모든 그래프를 연결하면서 각 간선의 양 끝 노드 번호의 합이 다르게 하는 방법은, (1, 2), (2, 3), .... , (N-1, N)으로 N-1개의 간선으로 연결하는 것이다. (일자형 트리)
그 다음에도 아직 M개의 간선이 연결되지 않았다면, 브루트포스로 모든 노드 쌍을 검사하면서 합이 나오지 않은 간선이라면 그 간선을 연결해주면 된다.
이외에는 모두 불가능한 경우이므로 -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);
int N, M; cin >> N >> M;
map<int, bool> m;
int cnt = 0;
vector<pair<int, int>> v;
for(int i=2; i<=N; i++) {
if(cnt == M) {
cout << -1 << "\n";
return 0;
}
v.push_back({i-1, i});
m[(i-1) + i] = true;
cnt++;
}
if(cnt == M) {
for(int j=0; j<v.size(); j++)
cout << v[j].first << " " << v[j].second << "\n";
return 0;
}
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
if(i == j) continue;
if(m[i+j]) continue;
v.push_back({i, j});
m[i + j] = true;
cnt++;
if(cnt == M) {
for(int j=0; j<v.size(); j++)
cout << v[j].first << " " << v[j].second << "\n";
return 0;
}
}
cout << -1 << "\n";
}
백준 BOJ 21316번 : 스피카
문제 난이도 : Silver III
알고리즘 분류 : 그래프 이론, 애드 혹
스피카 별자리와 같은 연결 관계의 그래프가 주어질 때, Spica 별에 대응되는 (연결 관계가 같은) 정점의 번호를 구하는 문제이다.
Spica 별에 해당하는 정점만이 가지고 있는 특징을 찾으면 된다.
해당 정점은 3개의 정점과 연결이 되어있고, 그 정점들은 각각 1, 2, 3개의 정점들과 연결되어 있다.
따라서 이 특성을 갖는 정점의 번호를 구해주면 된다.
#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>> adj(13);
for(int i=0; i<12; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=12; i++) {
if(adj[i].size() != 3) continue;
vector<bool> b(3);
for(int j=0; j<adj[i].size(); j++) {
int x = adj[i][j];
if(adj[x].size() == 1) b[0] = true;
if(adj[x].size() == 2) b[1] = true;
if(adj[x].size() == 3) b[2] = true;
}
if(b[0] && b[1] && b[2]) {
cout << i << "\n";
break;
}
}
}
백준 BOJ 6125번 : Treasure Cave
문제 난이도 : Silver II
알고리즘 분류 : 그래프 탐색 (트리)
N개의 노드와 M개의 갈림길을 가지고 있는 동굴의 구조가 주어질 때, 보물이 있는 노드까지 1번 노드로부터 들어가는 경로를 구하는 문제이다.
DFS를 스택처럼 구현하여 만약 해당 노드에서의 탐색이 끝나면 경로를 pop_back 해주고 돌아가는 식으로 하여 보물이 있는 노드를 방문할 때까지 반복하도록 하였다.
참고로 이 문제에서 주어지는 그래프는 트리 구조를 가지기 때문에 훨씬 간단하게 구현해도 풀렸을 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M, K;
vector<vector<int>> adj;
vector<bool> vis;
vector<int> v;
void f(int x) {
vis[x] = true;
v.push_back(x);
if(x == K) {
cout << v.size() << "\n";
for(int i=0; i<v.size(); i++) cout << v[i] << "\n";
return;
}
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(!vis[y]) f(y);
}
vis[x] = false;
v.pop_back();
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back(b);
adj[a].push_back(c);
}
vis.resize(N+1);
f(1);
}
백준 BOJ 1325번 : 효율적인 해킹
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색
a가 b를 신뢰하면 b를 해킹했을 때 a도 해킹할 수 있다고 할 때, 신뢰 관계로 연결된 그래프가 주어지면 어떤 컴퓨터를 해킹했을 때 최대로 많은 컴퓨터를 해킹할 수 있는지 그 번호를 구하는 문제이다.
위의 a, b 관계를 생각해보면 b에서 a로 간선을 잇고 한 노드를 선택하여 탐색했을 때 최대한 많은 노드들을 방문할 수 있으면 되므로, 브루트포스 비슷하게 모든 노드에 대해 출발점으로 설정하여 탐색해보면 된다.
시간 초과가 발생하지 않을까 했는데, 실버 난이도에 적절한 다른 풀이는 생각나지 않아서 그대로 제출했는데 맞았다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
int cnt;
void f(int x) {
vis[x] = true;
cnt++;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(!vis[y]) f(y);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[b].push_back(a);
}
int Max = 0;
vector<int> v;
for(int i=1; i<=N; i++) {
vis.clear();
vis.resize(N+1);
cnt = 0;
f(i);
if(cnt > Max) {
Max = cnt;
v.clear();
v.push_back(i);
}
else if(cnt == Max) v.push_back(i);
}
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
cout << "\n";
}
백준 BOJ 13379번 : Far Far Away
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색, 트리
트리가 주어질 때, 1번 노드에서부터 가장 먼 거리의 노드까지 도달하는 거리가 M 이상이면 그 거리를 출력하고, 그렇지 않으면 -1을 출력하는 문제이다.
간단한 그래프 탐색으로 해결해줄 수 있다.
다만 이 문제의 경우에는 간선의 길이가 주어지므로, adj 벡터에 거리까지 저장할 수 있도록 한다.
거리의 최댓값은 매 노드 방문 때마다 갱신해주면 된다.
트리는 사이클이 존재하지 않기 때문에 DFS로 탐색해도 무관하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> dis;
int Max = 0;
void f(int x) {
Max = max(Max, dis[x]);
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i].first;
if(dis[y] == -1) {
dis[y] = dis[x] + adj[x][i].second;
f(y);
}
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
adj.clear();
adj.resize(N+1);
for(int i=0; i<N-1; i++) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dis.clear();
dis.resize(N+1, -1);
dis[1] = 0;
Max = 0;
f(1);
if(Max >= M) cout << Max << "\n";
else cout << -1 << "\n";
}
}
백준 BOJ 5975번 : Pathfinding
문제 난이도 : Silver I
알고리즘 분류 : BFS
그래프가 주어질 때, i+1초에 도달할 수 있는 노드의 번호들을 i번째 줄에 오름차순으로 출력하는 문제이다.
애초에 입력에서 그래프 연결 관계가 인접 행렬로 주어지므로, 인접 행렬을 그대로 활용해주면 된다.
문제 조건에 따라 시간이 N-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);
int N, M; cin >> N >> M;
vector<vector<int>> adj(N+1, vector<int>(N+1));
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) cin >> adj[i][j];
vector<int> dis(N+1, -1);
dis[M] = 0;
queue<int> q;
q.push(M);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i=1; i<=N; i++) {
if(adj[x][i] == 0) continue;
if(dis[i] != -1) continue;
dis[i] = dis[x] + 1;
q.push(i);
}
}
int Max = 0;
for(int i=1; i<=N; i++)
Max = max(Max, dis[i]);
for(int i=0; i<=Max; i++) {
for(int j=1; j<=N; j++)
if(dis[j] == i) cout << j << " ";
cout << "\n";
}
}
백준 BOJ 4131번 : Modulo Solitaire
문제 난이도 : Silver II
알고리즘 분류 : BFS
주어진 M, N, S와 N개의 a, b 순서쌍에 대해 연산마다 하나의 a, b를 골라 S = (S * a + b) % M의 연산을 거쳐 0을 만드는 최소 연산 횟수를 구하는 문제이다.
M의 제한이 100만 이하이므로, 모든 수는 매 연산마다 항상 100만 이하의 값을 갖는다.
그러므로 100만 가지 정도의 모든 수에 대해 최소 도달 횟수를 기록할 수 있다.
따라서 BFS를 활용하여 답을 찾아주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int M, N, S; cin >> M >> N >> S;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++) cin >> v[i].first >> v[i].second;
vector<int> dis(1e6 + 1, -1);
dis[S] = 0;
queue<int> q;
q.push(S);
while(!q.empty()) {
int x = q.front();
q.pop();
if(x == 0) {
cout << dis[0] << "\n";
return 0;
}
for(int i=0; i<N; i++) {
int y = (x * v[i].first + v[i].second) % M;
if(y > 1e6) continue;
if(dis[y] != -1) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
cout << -1 << "\n";
}
백준 BOJ 12153번 : Counter Culture (Small)
문제 난이도 : Silver I
알고리즘 분류 : BFS
1부터 시작하여 1을 증가시키거나 수를 뒤집는 연산 중 하나를 수행하는 과정을 반복하여 N을 만드는데 필요한 최소 연산 횟수를 구하는 문제이다.
매 연산마다 2가지의 선택지가 있고, 수의 제한이 1e6 이하로 크지 않으므로 모든 경우를 다 따져볼 수 있다.
따라서 BFS를 이용하여 풀어주면 된다.
수를 뒤집을 경우 뒤집은 수가 N보다 크면 그 연산은 의미가 없으므로, queue에 다시 넣지 않는다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N; cin >> N;
vector<int> dis(N+1, -1);
dis[1] = 1;
queue<int> q;
q.push(1);
while(!q.empty()) {
int x = q.front();
q.pop();
if(x == N) {
cout << "Case #" << t << ": " << dis[x] << "\n";
break;
}
if(dis[x+1] == -1) {
dis[x+1] = dis[x] + 1;
q.push(x+1);
}
string temp = to_string(x);
reverse(temp.begin(), temp.end());
int y = stoll(temp);
if(y <= N && dis[y] == -1) {
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 풀이 : 그래프 이론 문제들 (Silver I ~ Gold) 220729 (0) | 2022.07.29 |
|---|---|
| 백준 BOJ 풀이 220728 (0) | 2022.07.28 |
| 백준 BOJ 풀이 : 오늘도 그래프 탐색 문제 220726 (0) | 2022.07.26 |
| 백준 BOJ 풀이 : BFS 문제들 위주 풀이 (그래프 탐색) 220725 (0) | 2022.07.25 |
| 백준 BOJ 풀이 : 데이크스트라, 이분 탐색, 그래프 등 220724 (0) | 2022.07.24 |