Algorithm/BOJ
[C/C++] 백준 알고리즘 수업 - 깊이 우선 탐색 문제 모음
poopooreum
2024. 4. 29. 18:50
반응형
✏️ 문제 링크
https://www.acmicpc.net/problem/24479
✏️ 문제 설명
✏️ 문제 풀이
단순 dfs를 구현하는 문제입니다. 다만 dfs를 탐색하면서 order[next] = order[node]+1로 하면 틀릴 수 있기 때문에
방문 순서를 체크해주는 count변수를 전역 변수로 설정하고 코드를 구현했습니다.
그리고 오름차순으로 방문을 해야하기 때문에 list를 각 노드마다 오름차순 정렬을 하였습니다.
이차원배열로 돌릴까 고민을 해봤는데 너무 메모리를 많이 잡아먹을 것 같아서 사용하지 않았습니다.
✏️ 문제 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool visit[100001];
int order[100001];
vector<vector<int>>list;
void dfs(int node);
int cnt = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
list.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
list[u].push_back(v);
list[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(list[i].begin(), list[i].end());
}
order[R] = cnt++;
dfs(R);
for (int i = 1; i <= N; i++)
cout << order[i] << "\n";
}
void dfs(int node) {
visit[node] = true;
for (int i : list[node]) {
if (visit[i])
continue;
order[i] = cnt++;
dfs(i);
}
}
✏️ 문제 링크
https://www.acmicpc.net/problem/24480
✏️ 문제 설명
✏️ 문제 풀이
24479번과 거의 동일한 문제이나 내림차순으로 정점을 방문해야 합니다.
따라서 위의 문제처럼 정렬을 한 후에 dfs함수에서 방문순서를 리스트의 마지막부분부터 탐색하면 됩니다.
✏️ 문제 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool visit[100001];
int order[100001];
vector<vector<int>>list;
void dfs(int node);
int cnt = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
list.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
list[u].push_back(v);
list[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(list[i].begin(), list[i].end());
}
order[R] = cnt++;
dfs(R);
for (int i = 1; i <= N; i++)
cout << order[i] << "\n";
}
void dfs(int node) {
visit[node] = true;
for (int i = list[node].size() - 1; i >= 0; i--) {
int next = list[node][i];
if (visit[next])
continue;
order[next] = cnt++;
dfs(next);
}
}✏️ 문제 링크
https://www.acmicpc.net/problem/24481
✏️ 문제 설명
✏️ 문제 풀이
이 문제는 각 노드의 깊이를 구하는 문제입니다. 따라서 깊이를 저장할 depth배열(처음에 -1로 초기화)을 생성하고
dfs를 탐색하면서 방문하지 않은 노드에 대하여 depth[방문할 노드] = depth[방문했던 노드] + 1로 설정하면 됩니다.
✏️ 문제 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool visit[100001];
int depth[100001];
vector<vector<int>>list;
void dfs(int node);
int cnt = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
list.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
list[u].push_back(v);
list[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(list[i].begin(), list[i].end());
}
for (int i = 0; i < 100001; i++)
depth[i] = -1;
depth[R] = 0;
dfs(R);
for (int i = 1; i <= N; i++)
cout << depth[i] << "\n";
}
void dfs(int node) {
visit[node] = true;
for (int next : list[node]) {
if (visit[next])
continue;
depth[next] = depth[node] + 1;
dfs(next);
}
}
✏️ 문제 링크
https://www.acmicpc.net/problem/24482
✏️ 문제 설명
✏️ 문제 풀이
24481번과 거의 비슷하고 내림차순으로 인접 정점을 방문하시면 됩니다.
24481번처럼 코드를 구현하고 정점을 탐색하는 순서를 리스트의 마지막부터 탐색하시면 됩니다.
✏️ 문제 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool visit[100001];
int depth[100001];
vector<vector<int>>list;
void dfs(int node);
int cnt = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
list.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
list[u].push_back(v);
list[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(list[i].begin(), list[i].end());
}
for (int i = 0; i < 100001; i++)
depth[i] = -1;
depth[R] = 0;
dfs(R);
for (int i = 1; i <= N; i++)
cout << depth[i] << "\n";
}
void dfs(int node) {
visit[node] = true;
for (int i = list[node].size() - 1; i >= 0; i--) {
int next = list[node][i];
if (visit[next])
continue;
depth[next] = depth[node] + 1;
dfs(next);
}
}
✏️ 문제 링크
https://www.acmicpc.net/problem/24483
✏️ 문제 설명
✏️ 문제 풀이
위에서 풀었던 문제들을 모두 사용하는 문제입니다. 각 노드에 대해서 정점 순서와 깊이를 저장하고 이를 곱해서
더한 값을 출력하는 문제입니다. 조심해야 할 점으로는 int형으로 설정하면 오버플로우가 발생할 수 있기 때문에
long long형으로 설정해서 문제에 접근하셔야 합니다.
✏️ 문제 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
bool visit[100001];
ll depth[100001];
ll order[100001];
vector<vector<int>>list;
void dfs(int node);
ll cnt = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
list.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
list[u].push_back(v);
list[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(list[i].begin(), list[i].end());
}
for (int i = 0; i < 100001; i++)
depth[i] = -1;
depth[R] = 0;
order[R] = cnt++;
dfs(R);
ll res = 0;
for (int i = 1; i <= N; i++) {
ll mul= depth[i] * order[i];
res += mul;
}
cout << res;
}
void dfs(int node) {
visit[node] = true;
for(int next:list[node]) {
if (visit[next])
continue;
depth[next] = depth[node] + 1;
order[next] = cnt++;
dfs(next);
}
}✏️ 문제 링크
https://www.acmicpc.net/problem/24484
✏️ 문제 설명
✏️ 문제 풀이
24483번과 동일하며 정점을 탐색할 때 리스트의 마지막 노드부터 탐색을 해야 합니다.
✏️ 문제 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
bool visit[100001];
ll depth[100001];
ll order[100001];
vector<vector<int>>list;
void dfs(int node);
ll cnt = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin >> N >> M >> R;
list.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
list[u].push_back(v);
list[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(list[i].begin(), list[i].end());
}
for (int i = 0; i < 100001; i++)
depth[i] = -1;
depth[R] = 0;
order[R] = cnt++;
dfs(R);
ll res = 0;
for (int i = 1; i <= N; i++) {
ll mul = depth[i] * order[i];;
res += mul;
}
cout << res;
}
void dfs(int node) {
visit[node] = true;
for (int i = list[node].size() - 1; i >= 0; i--) {
int next = list[node][i];
if (visit[next])
continue;
depth[next] = depth[node] + 1;
order[next] = cnt++;
dfs(next);
}
}
✏️ etc..
다시 기초부터 폐관수련 하겠습니다...
반응형