https://www.acmicpc.net/problem/24479
24479번: 알고리즘 수업 - 깊이 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양
www.acmicpc.net
이 문제의 경우 쉽다 dfs 는 자기 자식으로 쭉내려가기 때문에 일단 자기 자식들중 방문하지 않은 자식있으면 재귀로 쭉쭉내려간다 갈 수 없는곳을 만나면 자기 부모로 돌아가 갈 수 있는 곳을 다시 탐색하는걸 반복한다 그렇기 때문에 일단 재귀로 콜한다음 자기자식이 방문했는지 아닌지 검사하고 방문했으면 conitnue 문을 통해 방문을 건너뛴다 재귀기 때문에 갈곳이 없어 리턴되면 자기자신의 부모가 갈곳을 탐색한다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> vertex[200001];
int visitednum[100001];
bool visited[100001] = { false, };
int countnum = 0;
void dfs(int start) {
countnum += 1;
visitednum[start] = countnum;
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true) {
continue;
}
dfs(vertex[start][i]);
}
}
int main() {
int vertexnum, edgenum, startvertex;
cin >> vertexnum >> edgenum >> startvertex;
for (int i = 1; i <= edgenum; i++) {
int temp1 = 0;
int temp2 = 0;
cin >> temp1 >> temp2;
vertex[temp1].push_back(temp2);
vertex[temp2].push_back(temp1);
}
for (int i = 1; i <= vertexnum; i++) {
sort(vertex[i].begin(), vertex[i].end());
}
dfs(startvertex);
for (int i = 1; i <= vertexnum; i++) {
cout << visitednum[i]<<'\n';
}
}일단 위에 코드를 보게되면 visitednum이라는 것이 존재 한다 visitednum은 i번째가 루트로부터 몇번째에 갈 수 있는지를 visitednum[i] 에 저장 해준다 이것을 이용해 후에 답을 출력할 것이다. 개인적으로 배열을 써야하는 알고리즘 문제들은 visualstudio에서 stack 사이즈 문제로 오류를 엄청 띄우기 때문에 거의 전역으로 설정 해주는게 좋다. 뭐 다음 코드는 이전글에 있는 DFS BFS 알고리즘 문제에 있는 방식과 똑같다 나랑연결되 있는애들을 나의 vertex에 넣어 준다.
예시로 백준에 input값을 보자
5 5 1
1 4
1 2
2 3
2 4
3 4이런식으로 입력을 받아오면
vertex[1]에는 4,2
vertex[2]에는 1,3,4
vertex[3]에는 2,4
vertex[4]에는 1,2,3
이 들어가게 된다 DFS에서의 간선은 양방향으로 갈수 있기때문에 양쪽에 값을 넣어 준 것 이다. 그 이후에 이 vector를 오름차 순으로 정렬해주고 나와 연결된애에게로 간다 지금 상황에선 2부터 쭉가서 끝까지 간다 쭉가다가 더 이상 갈 수 없으면 재귀함수는 return으로 자기 caller에게 돌아가기 때문에 자기 부모로 돌아가게된다 그후 부모도 다른 곳으로 갈 수 있는 지 없는지 판단하고 자기자신의 부모로 간다 이렇게 반복되어 DFS가 완성된다