백준 BOJ 20040번 : 사이클 게임
문제 난이도 : Gold IV
알고리즘 분류 : 분리 집합
N개의 정점이 있는 그래프에 M개의 간선을 연결할 때 몇 번째 간선부터 사이클이 생기는지를 구하는 문제이다.
사이클의 발생은 두 노드를 간선으로 연결하기 전에 두 노드가 이미 연결 관계인 경우 발생한다.
따라서 분리 집합을 이용하여 연결 관계를 체크해주다가 두 노드 사이가 연결 관계라면 해당 번째 번호를 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0;
for(int i=1; i<=M; i++) {
int a, b; cin >> a >> b;
if(f(a) == f(b) && ans == 0) ans = i;
v[f(a)] = f(b);
}
cout << ans << "\n";
}
백준 BOJ 10216번 : Count Circle Groups
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합
각 통신탑의 좌표와 통신 거리가 주어지고, 연결을 통해 통신 가능한 통신탑들을 하나의 그룹으로 볼 때 총 그룹의 수를 구하는 문제이다.
N이 3,000 이하이고 제한 시간이 8초로 아주 넉넉하므로, O(N^2) 풀이가 당연히 가능하다.
따라서 모든 통신탑의 쌍을 찾아 피타고라스의 정리를 이용하여 거리를 구해주고 통신이 가능한 경우 간선으로 연결해준다.
연결이 끝난 이후 disjoint set을 이용하여 그룹의 수를 세주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int x, y, r; };
vector<int> u;
int f(int x) {
if(u[x] == x) return x;
else return u[x] = f(u[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
vector<s> v(N);
for(int i=0; i<N; i++)
cin >> v[i].x >> v[i].y >> v[i].r;
u.clear();
u.resize(N);
for(int i=0; i<N; i++) u[i] = i;
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++) {
if(f(i) == f(j)) continue;
if(pow(v[i].x - v[j].x, 2) + pow(v[i].y - v[j].y, 2) > pow(v[i].r + v[j].r, 2)) continue;
u[f(i)] = f(j);
}
vector<int> w(N);
for(int i=0; i<N; i++) w[i] = f(i);
sort(w.begin(), w.end());
w.erase(unique(w.begin(), w.end()), w.end());
cout << w.size() << "\n";
}
}
백준 BOJ 6207번 : Cow Picnic
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색
그래프와 각 소의 위치가 주어질 때, 모든 소들이 모일 수 있는 정점의 수를 구하는 문제이다.
먼저 입력된 그래프대로 그래프를 구현해주고, 정점의 수의 제한이 1,000 이하로 별로 크지 않으므로 O(N^2)이 통과되기 때문에 모든 점들에 대해 소들이 모일 수 있는지 체크해보면 된다.
소의 초기 위치가 주어지기 때문에 별도의 벡터를 선언하여 이들의 위치를 저장해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<vector<bool>> vis;
int cur;
void f(int x) {
vis[cur][x] = true;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(!vis[cur][y]) f(y);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
adj.resize(M+1);
while(K--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
}
vis.resize(N, vector<bool>(M+1));
for(int i=0; i<N; i++) {
cur = i;
f(v[i]);
}
int ans = 0;
for(int i=1; i<=M; i++) {
bool check = true;
for(int j=0; j<N; j++)
if(!vis[j][i]) check = false;
if(check) ans++;
}
cout << ans << "\n";
}
백준 BOJ 5931번 : Cow Beauty Pageant
문제 난이도 : Silver I
알고리즘 분류 : BFS
2차원 배열에 두 덩어리의 X가 주어질 때, 두 덩어리를 연결하기 위한 최소 격자 수를 구하는 문제이다.
BFS 문제이나 BFS를 수행하기 전에 두 덩어리를 다른 값으로 처리를 해주어야 한다.
왜냐하면 같은 덩어리로 돌아오도록 다리가 연결될 수도 있는데 이를 구분할 수 없기 때문이다.
참고로 이 문제는 백준 BOJ 2146번 : 다리 만들기와 동일한 문제이다.
해당 문제의 풀이는 이 링크에 작성해 두었으니 참고하면 좋을 것이다.
#include <bits/stdc++.h>
#define MAX 101
using namespace std;
int N, M;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int arr[MAX][MAX], vis[MAX][MAX];
void clear_vis() {
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) vis[i][j] = 0;
}
int color = 2;
void coloring(int x, int y) {
vis[x][y] = 1;
arr[x][y] = color;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(vis[nx][ny] == 0 && arr[nx][ny] == 1) coloring(nx, ny);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
char c; cin >> c;
if(c == 'X') arr[i][j] = 1;
else arr[i][j] = 0;
}
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
if(arr[i][j] == 1) {
clear_vis();
coloring(i, j);
color++;
}
int ans = INT_MAX;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
if(arr[i][j] != 0) {
clear_vis();
queue<pair<int, int>> q;
int curr_color = arr[i][j];
for(int k=0; k<4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(arr[nx][ny] == 0) {
q.push({nx, ny});
vis[nx][ny] = 1;
}
}
while(!q.empty()) {
int x = q.front().first;
int 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(arr[nx][ny] != 0 && arr[nx][ny] != curr_color && vis[nx][ny] == 0) {
vis[nx][ny] = vis[x][y] + 1;
ans = min(ans, vis[x][y]);
}
if(arr[nx][ny] == 0 && vis[nx][ny] == 0) {
vis[nx][ny] = vis[x][y] + 1;
q.push({nx, ny});
}
}
}
}
cout << ans;
}
백준 BOJ 1743번 : 음식물 피하기
문제 난이도 : Silver I
알고리즘 분류 : DFS, BFS
음식물들의 좌표가 주어질 때 상하좌우로 인접한 가장 큰 음식물의 크기를 구하는 문제이다.
단순한 탐색 문제로, 입력되는 좌표들의 값을 표시해주고 모든 좌표에 대해 visit 여부를 체크하며 DFS 또는 BFS 등의 탐색을 수행하면서 count 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> v;
vector<vector<bool>> vis;
int N, M, K, cnt;
void f(int x, int y) {
vis[x][y] = true;
cnt++;
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 >= N || ny >= M) continue;
if(vis[nx][ny] || v[nx][ny] != 1) continue;
f(nx, ny);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M >> K;
v.resize(N, vector<int>(M));
while(K--) {
int a, b; cin >> a >> b;
v[a-1][b-1] = 1;
}
vis.resize(N, vector<bool>(M));
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
if(v[i][j] == 1 && !vis[i][j]) {
cnt = 0;
f(i, j);
ans = max(ans, cnt);
}
cout << ans << "\n";
}
백준 BOJ 6059번 : Pasture Walking
문제 난이도 : Silver II
알고리즘 분류 : 그래프 탐색
트리 그래프가 주어질 때 주어진 쿼리에 대해 두 정점 사이의 거리들을 구하는 문제이다.
정점의 수가 1,000개 이하이므로, 모든 쿼리에 대해 각각 값을 구해보아도 시간이 충분하다.
따라서 재귀함수를 이용하여 DFS와 비슷하게 거리를 구하는 함수를 구현하여 답을 구해주는 방식을 사용했다.
visit 여부를 체크하지 않고 이전 노드가 아닌 다른 인접한 노드를 방문하여 거리를 구하도록 구현했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<pair<int, int>>> adj;
int ans, dest;
void f(int cur, int pre, int sum) {
if(cur == dest) {
ans = sum;
return;
}
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
if(nex != pre) f(nex, cur, sum + adj[cur][i].second);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
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});
}
while(M--) {
int a, b; cin >> a >> b;
dest = b;
ans = 0;
f(a, 0, 0);
cout << ans << "\n";
}
}
백준 BOJ 19583번 : 싸이버개강총회
문제 난이도 : Silver II
알고리즘 분류 : 해시를 사용한 집합과 맵
총회 시작 전 채팅 로그와 총회가 끝난 뒤 채팅 로그를 둘 다 남긴 사람들만 출석을 인정할 때 출석이 인정된 사람의 수를 구하는 문제이다.
사람들의 목록은 시간과 이름 순으로 주어지는데, 이 때 유용한 팁은 시간은 단순히 문자열의 사전순으로 비교할 수 있다는 것이다.
예를 들어 22:30과 23:01이 입력되었다면, 두 문자열을 a와 b로 받아 a < b임을 체크하여 a가 b보다 앞선 시간임을 알 수 있다.
나머지는 해시를 사용한 집합과 맵을 사용하여 총회 시작 전과 후의 로그를 체크하여 둘 다 확인되는 경우에만 count 해주어 답을 구해주기만 하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
string a, b, c; cin >> a >> b >> c;
map<string, bool> m1, m2;
string x, y;
vector<string> v;
while(cin >> x >> y) {
if(x <= a) m1[y] = true;
else if(x >= b && x <= c) m2[y] = true;
v.push_back(y);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int ans = 0;
for(int i=0; i<v.size(); i++)
if(m1[v[i]] && m2[v[i]]) ans++;
cout << ans << "\n";
}
백준 BOJ 24446번 : 알고리즘 수업 - 너비 우선 탐색 3
문제 난이도 : Silver II
알고리즘 분류 : BFS
N개의 정점과 M개의 간선, 시작 노드 K가 주어질 때 각 노드까지의 거리를 구하는 문제이다.
단순 BFS 구현 문제이므로, 거리를 -1로 초기화 해주고 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 N, M, K; cin >> N >> M >> K;
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> dis(N+1, -1);
dis[K] = 0;
queue<int> q;
q.push(K);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(dis[y] != -1) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
for(int i=1; i<=N; i++) cout << dis[i] << "\n";
}
백준 BOJ 24447번 : 알고리즘 수업 - 너비 우선 탐색 4
문제 난이도 : Silver II
알고리즘 분류 : BFS
그래프가 주어지고 K번 노드에서 시작하여 모든 노드에 대해 측정한 방문 순서 a_i와 노드의 깊이 b_i에 대해서, a_i * b_i의 합을 구하는 문제이다.
먼저 한 노드에서 방문하는 노드들의 순서 기준은 번호의 오름차순이므로, 각 노드에 대해 adj 값들을 오름차순 정렬을 해준다.
그 다음 cnt 값을 1에서부터 증가시켜가면서 방문할 때마다 cnt 값을 배정하여 방문 순서를 저장해준다.
거리는 위의 문제와 동일하게 BFS로 구해주고, 방문할 수 있는 노드에 한정하여 a_i * b_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, K; cin >> N >> M >> K;
vector<vector<int>> adj(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end());
vector<int> dis(N+1, -1);
dis[K] = 0;
queue<int> q;
q.push(K);
int cnt = 1;
vector<int> v(N+1);
v[K] = cnt++;
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(dis[y] != -1) continue;
dis[y] = dis[x] + 1;
v[y] = cnt++;
q.push(y);
}
}
int ans = 0;
for(int i=1; i<=N; i++)
if(dis[i] != -1) ans += dis[i] * v[i];
cout << ans << "\n";
}
백준 BOJ 24881번 : 알고리즘 수업 - 깊이 우선 탐색 3
문제 난이도 : Silver II
알고리즘 분류 : DFS
그래프가 주어질 때 K번 노드에서부터 각 노드까지 DFS로 측정했을 때 깊이를 구하는 문제이다.
단순 DFS 구현 문제이므로 DFS를 구현해주면 된다.
주의해야할 점은 그래프에 사이클이 존재할 수 있으므로 반드시 특정 노드에 대해 연결된 정점을 방문할 때 번호의 오름차순으로 방문할 수 있도록, adj 벡터의 오름차순 정렬을 미리 수행한 상태에서 DFS를 수행해주어야 한다는 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<int> dis;
void f(int x) {
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(dis[y] == -1) {
dis[y] = dis[x] + 1;
f(y);
}
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end());
dis.resize(N+1, -1);
dis[K] = 0;
f(K);
for(int i=1; i<=N; i++) cout << dis[i] << "\n";
}
참고로 백준 BOJ 24882번 : '알고리즘 수업 - 깊이 우선 탐색 4'는 이 문제와 동일하나 한 노드에서 다른 노드로 방문할 때 번호의 내림차순 순서로 방문하는 문제이다.
단순히 adj 벡터에 대해 정렬 부분의 구현만 내림차순으로 구현해주면 된다.
백준 BOJ 24883번 : 알고리즘 수업 - 깊이 우선 탐색 5
문제 난이도 : Silver II
알고리즘 분류 : DFS
백준 BOJ 24447번과 동일하나 DFS를 이용하여 답을 구하는 문제이다.
똑같이 구현하되 BFS만 DFS로 바꾸어 구현해주면 된다.
전역변수에 cnt = 1로 두고 노드를 방문할 때마다 cnt를 1씩 증가시켜 배정해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<int> dis, v;
int cnt = 1;
void f(int x) {
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(dis[y] == -1) {
dis[y] = dis[x] + 1;
v[y] = cnt++;
f(y);
}
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end());
dis.resize(N+1, -1);
dis[K] = 0;
v.resize(N+1);
v[K] = cnt++;
f(K);
int ans = 0;
for(int i=1; i<=N; i++)
if(dis[i] != -1) ans += dis[i] * v[i];
cout << ans << "\n";
}
참고로 백준 BOJ 24484번 : '알고리즘 수업 - 깊이 우선 탐색 6' 문제의 경우 이 문제와 거의 동일하나 정점의 정렬 순서만 내림차순으로 정렬해주면 똑같이 정답 처리를 받을 수 있다.
백준 BOJ 5567번 : 결혼식
문제 난이도 : Silver II
알고리즘 분류 : 그래프 탐색
문제를 요약하면 1번 노드로부터 1칸 떨어진 노드와 2칸 떨어진 노드들의 수를 구하는 문제이다.
다양한 방법으로 구할 수 있겠지만, 나의 경우에는 마땅한 방법이 생각나지 않아 BFS로 해결하였다.
1번 노드부터 BFS를 수행하여 모든 노드에 대해 거리를 기록한 뒤, 거리가 1 또는 2인 노드의 수를 count 하여 답으로 출력하였다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<int> vis;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
adj.resize(N+1);
int M; cin >> M;
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vis.resize(N+1, -1);
vis[1] = 0;
queue<int> q;
q.push(1);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(vis[y] != -1) continue;
vis[y] = vis[x] + 1;
q.push(y);
}
}
int ans = 0;
for(int i=1; i<=N; i++)
if(vis[i] == 1 || vis[i] == 2) ans++;
cout << ans << "\n";
}
백준 BOJ 11370번 : Spawn of Ungoliant
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색
주어진 2차원 배열에 대해 S가 상하좌우로 인접한 T로 전파된다고 할 때, 전파된 이후의 2차원 배열을 출력하는 문제이다.
역시 간단한 그래프 탐색 문제에 해당한다.
매 테스트케이스마다 배열 등의 변수들을 초기화해줘야 하는 번거로움이 있어 DFS보다는 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);
while(true) {
int N, M; cin >> M >> N;
if(N == 0 && M == 0) break;
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];
vector<vector<bool>> vis(N, vector<bool>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(v[i][j] != 'S') continue;
queue<pair<int, int>> q;
q.push({i, j});
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
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(vis[nx][ny] || v[nx][ny] != 'T') continue;
vis[nx][ny] = true;
v[nx][ny] = 'S';
q.push({nx, ny});
}
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) cout << v[i][j];
cout << "\n";
}
}
}
백준 BOJ 11448번 : Ga
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색
보드에서 '-' 문자가 빈 칸이라고 할 때, w의 상하좌우 대각선 8방향으로 이어서 새로 w를 둘 수 있는 칸의 수를 구하는 문제이다.
단순 그래프 탐색 문제로, 모든 칸에 대해 브루트포스로 검사하면서 8방향에 대해 w와 인접한지를 탐색해주고 새로 놓을 수 있는 칸들을 모두 count 해주면 된다.
#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;
while(T--) {
int N; cin >> N;
vector<vector<char>> v(N, vector<char>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
vector<vector<bool>> vis(N, vector<bool>(N));
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) {
if(v[i][j] != 'w' || vis[i][j]) continue;
queue<pair<int, int>> q;
q.push({i, j});
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
for(int k=0; k<8; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if(v[nx][ny] != '-' || vis[nx][ny]) continue;
v[nx][ny] = 'w';
vis[nx][ny] = true;
q.push({nx, ny});
ans++;
}
}
}
cout << ans << "\n";
}
}
백준 BOJ 3182번 : 한동이는 공부가 하기 싫어!
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색
각 노드가 가리키는 번호로 이동하여 만들 수 있는 가장 큰 사이클의 크기를 구하는 문제이다.
노드의 수가 1,000개 이하이므로 모든 노드에 대해 시작점으로 잡아보면서 사이클의 크기를 구해보면 된다.
사이클의 크기를 측정할 때는 bool 변수로 방문 여부만 저장하면서, 최대 사이클의 크기가 N이기 때문에 N번만 이동해보면 된다.
#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; cin >> N;
vector<int> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i];
int Max = 0, ans;
for(int i=1; i<=N; i++) {
vector<bool> u(N+1);
int cur = i;
for(int j=0; j<N; j++) {
u[cur] = true;
cur = v[cur];
}
int cnt = 0;
for(int i=1; i<=N; i++)
if(u[i]) cnt++;
if(cnt > Max) {
Max = cnt;
ans = i;
}
}
cout << ans << "\n";
}
백준 BOJ 5938번 : Daisy Chains in the Field
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색
N마리의 소에 대해 M개의 소 쌍에 대한 연결 관계가 주어질 때, 1번 소와 연결 관계가 아닌 소들의 번호를 출력하는 문제이다.
간단한 그래프 탐색 문제로, 그래프 연결을 수행해주고 1번 소에 대해 DFS를 수행해주면 된다.
방문하지 않은 노드들을 번호 순으로 출력해주면 정답 처리를 받을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
void f(int x) {
vis[x] = true;
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[a].push_back(b);
adj[b].push_back(a);
}
vis.resize(N+1);
f(1);
bool check = false;
for(int i=1; i<=N; i++)
if(!vis[i]) {
cout << i << "\n";
check = true;
}
if(!check) cout << 0 << "\n";
}
백준 BOJ 10204번 : Neighborhoods in Graphs
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색 (BFS)
주어진 그래프와 노드에 대해, 노드로부터 거리가 1 또는 2인 노드의 개수를 구하는 문제이다.
먼저 노드 번호가 1, 2 처럼 숫자로 주어지는 것이 아니라 v1, v2와 같이 주어지므로 문자열 처리를 한 번 해주어야 한다.
그래프 탐색을 수행하여 거리를 구해주면 되는데, 이 문제의 경우 주어지는 그래프에 사이클이 존재하므로 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 T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
vector<vector<int>> adj(N+1);
while(M--) {
string a, b; cin >> a >> b;
int x = stoi(a.substr(1, a.length()-1));
int y = stoi(b.substr(1, b.length()-1));
adj[x].push_back(y);
adj[y].push_back(x);
}
string str; cin >> str;
int s = stoi(str.substr(1, str.length()-1));
vector<int> vis(N+1, -1);
vis[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(vis[y] == -1) {
vis[y] = vis[x] + 1;
q.push(y);
}
}
}
int ans = 0;
for(int i=1; i<=N; i++)
if(vis[i] == 1 || vis[i] == 2) ans++;
cout << "The number of supervillains in 2-hop neighborhood of v"
<< s << " is " << ans << "\n";
}
}
백준 BOJ 11558번 : The Game of Death
문제 난이도 : Silver IV
알고리즘 분류 : 그래프 탐색
1번부터 N번까지의 사람이 각자 가리킬 번호를 부르고, 1번부터 시작하여 부른 번호의 사람으로 이동하는 과정을 거칠 때 N번 사람으로 이동하기 위해서는 몇 번의 이동이 필요한지를 구하는 문제이다.
그래프 탐색 문제로, 각 노드에 대해 부모 노드를 저장해주고 부모 노드로 계속 이동해주면서 N번 노드가 몇 번째에 나오는지 찾으면 된다.
사이클은 최대 N의 크기를 가지므로 N번의 이동을 거쳤음에도 N번 노드에 도달하지 못했다면 1번 노드와 N번 노드는 연결 관계가 아닌 것이므로 0을 출력해주면 된다.
#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;
while(T--) {
int N; cin >> N;
vector<int> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i];
int ans = 1, cur = 1;
while(true) {
if(v[cur] == N) {
cout << ans << "\n";
break;
}
cur = v[cur];
ans++;
if(ans > N) {
cout << 0 << "\n";
break;
}
}
}
}
백준 BOJ 22945번 : 팀 빌딩
문제 난이도 : Gold IV
알고리즘 분류 : 두 포인터
길이 N인 수열이 주어지고 v[i], v[j]를 선택했을 때 얻는 값이 (j-i-1) * min(v[i], v[j])일 때 얻을 수 있는 값의 최대를 구하는 문제이다.
N이 10만 이하이므로 당연히 O(N^2)에는 안된다.
조금 생각해보면 브루트포스 알고리즘은 비효율적임을 알 수 있는데, 그 이유는 답으로 가능한 후보가 별로 없기 때문이다.
가장 간단한 풀이는, i = 0, j = N-1에서 시작하여 투 포인터 알고리즘으로 풀이하는 것이다.
만약 v[i] < v[j]라면 반드시 i를 오른쪽으로 이동시켜야 더 높은 값을 얻을 가능성이라고 얻을 수 있다.
왜냐하면 이 경우에서 j를 왼쪽으로 이동시킬 경우 min 값은 같거나 더 작아질 수 밖에 없기 때문이다.
#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; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int i = 0, j = N-1, ans = INT_MIN;
while(i < j) {
int x = (j-i-1) * min(v[i], v[j]);
ans = max(ans, x);
if(v[i] < v[j]) i++;
else j--;
}
cout << ans << "\n";
}
백준 BOJ 25375번 : 아주 간단한 문제
문제 난이도 : Silver V
알고리즘 분류 : 정수론
주어진 a, b에 대해 gcd(x, y) = a이고, x + y = b인 순서쌍 (x, y)가 존재하는지를 구하는 문제이다.
gcd(x, y) = a라는 부분에서 x = ax', y = ay'으로 잡을 수 있으며 x + y = ax' + ay' = a(x' + y') = b이다.
따라서 b가 a보다 큰 배수이면, x' = 1, y' = b/a - 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 T; cin >> T;
while(T--) {
int a, b; cin >> a >> b;
if(b % a == 0 && b > a) cout << 1 << "\n";
else cout << 0 << "\n";
}
}
백준 BOJ 17224번 : APC는 왜 서브태스크 대회가 되었을까?
문제 난이도 : Bronze I
알고리즘 분류 : 구현
문제의 수, 각 배점에 따른 난이도, 풀 수 있는 난이도, 시간 내에 풀 수 있는 문제 수가 주어질 때 얻을 수 있는 점수의 최댓값을 구하는 문제이다.
몇 점짜리 문제를 푸나 받는 점수는 동일하므로 140점짜리 문제를 모두 시도해보고, 그 다음 100점짜리 문제들을 시도해보면 된다.
난이도에 대해 정렬을 해줬는데 지금 생각해보니 굳이 정렬을 해줄 필요가 없었던 것 같다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b; bool c; };
bool cmp1(s x, s y) {
return x.b < y.b;
}
bool cmp2(s x, s y) {
return x.a < y.a;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<s> v(N);
for(int i=0; i<N; i++) cin >> v[i].a >> v[i].b;
sort(v.begin(), v.end(), cmp1);
int cnt = 0, ans = 0;
if(K == 0) {
cout << ans << "\n";
return 0;
}
for(int i=0; i<N; i++) {
if(M >= v[i].b) {
cnt++;
ans += 140;
v[i].c = true;
}
if(cnt == K) {
cout << ans << "\n";
return 0;
}
}
sort(v.begin(), v.end(), cmp2);
for(int i=0; i<N; i++) {
if(M >= v[i].a && !v[i].c) {
cnt++;
ans += 100;
}
if(cnt == K) {
cout << ans << "\n";
return 0;
}
}
cout << ans << "\n";
}
백준 BOJ 25373번 : 벼락치기
문제 난이도 : Bronze II
알고리즘 분류 : 수학
7일간 N개의 영상을 보는데 하루에 보는 영상의 개수가 전날 본 영상의 수보다 적어야한다고 할 때 첫 날 보아야 할 영상의 최소 개수를 구하는 문제이다.
구현이 까다롭고, 많은 조건 분기라는 알고리즘 태그가 붙어서 그냥 구현하기는 고려해야 할 조건이 많을 것 같아 이분 탐색으로 접근하였다.
첫 날 보는 영상의 수가 m이라고 할 때 7일간 보는 영상의 개수는 7m - 21이라고 두고 풀었는데, 문제는 m이 아주 작은 경우 음수가 되기 때문에 이렇게 구하지 말고 for문으로 7일간의 영상의 개수를 따로 더해주어야 한다는 번거로움이 있었다.
자세한 것은 코드를 참조하면 도움이 될 것이다.
#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; cin >> N;
int l = 0, r = 1e17;
while(l <= r) {
int m = (l + r)/2;
int x = 0;
for(int i=0; i<7; i++) x += max(m - i, (int)0);
if(x >= N) r = m - 1;
else l = m + 1;
}
cout << l << "\n";
}
백준 BOJ 2909번 : 캔디 구매
문제 난이도 : Bronze II
알고리즘 분류 : 구현
물건의 가격과 화폐 단위가 주어졌을 때 화폐 단위의 배수가 되도록 가장 낮은 자리에서 반올림한 값을 구하는 문제이다.
C++에는 소수점 첫째자리에서 반올림을 해주는 round 함수가 있으므로, 반올림할 자리까지 수를 10의 거듭제곱으로 나눠준 뒤 반올림을 수행하고 다시 10의 거듭제곱을 곱해주는 방식을 떠올리고 구현해보았다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
double a, b; cin >> a >> b;
a /= pow(10, b);
int ans = round(a) * pow(10, b);
cout << ans << "\n";
}
백준 BOJ 13998번 : 연속합 2
문제 난이도 : Gold V
알고리즘 분류 : DP
N개의 정수로 이루어진 수열에서 구간 합 또는 정수 1개를 지운 수열에서의 구간 합의 최댓값을 구하는 문제이다.
N이 10만 이하이므로, O(N^2) 풀이는 불가능하고 그렇다고 정렬이나 분할 정복을 사용할만한 문제도 아니므로 O(N)에 풀 생각을 해야한다.
dp 배열을 2개를 선언하여, 하나는 수를 지우지 않고 얻은 최대 부분 합을 저장하고, 나머지 하나는 수 하나를 지운 상태에서 얻은 최대 부분 합을 저장해준다.
dp[i][0]은 0~i번째 수열에서의 최대 부분합, dp[i][1]은 0~i번째 수열에서 수를 하나 지운 수열에서의 최대 부분합이라고 정의하자.
그러면 점화식은 다음과 같다. : dp[i][0] = max(dp[i-1][0], 0) + v[i], dp[i][1] = max(dp[i-1][0], dp[i-1][1] + v[i])
이와 별개로 초깃값 설정에서 약간 고민을 했는데, 제출해보니 dp[0][1] = a_0으로 두어도 답에는 문제가 없는 것으로 보인다.
왜냐하면 테스트케이스에 길이 1짜리 수열이 입력으로 들어올 수도 있고, 수를 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; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int dp[100001][2] = {{v[0], v[0]}};
for(int i=1; i<N; i++) {
dp[i][0] = max(dp[i-1][0], (int)0) + v[i];
dp[i][1] = max(dp[i-1][0], dp[i-1][1] + v[i]);
}
int ans = INT_MIN;
for(int i=0; i<N; i++) ans = max({ans, dp[i][0], dp[i][1]});
cout << ans << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 220720 백준 BOJ 풀이 : LIS (가장 긴 증가하는 부분 수열) 문제들 (0) | 2022.07.20 |
|---|---|
| 220719 백준 풀이 : BOJ 18977, BOJ 25369, BOJ 25370 등 (0) | 2022.07.19 |
| 220717 백준 BOJ 풀이 : 2차원 배열 탐색, 정렬 문제 등 풀이 (0) | 2022.07.17 |
| 220716 PS 일기 : 조합론(DP), 카탈란 수 문제들 위주 풀이 (0) | 2022.07.16 |
| 220715 PS 일기 : 탐색(DFS, BFS, 백트래킹), 그리디 쉬운 문제들 (실버 ~ 골드) (0) | 2022.07.15 |