[C/C++] 백준 알고리즘 수업 - 깊이 우선 탐색 문제 모음

✏️ 문제 링크

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..

다시 기초부터 폐관수련 하겠습니다...