백준 24480

 

https://www.acmicpc.net/problem/24480

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

이문제의 경우도 DFS의 개념을 알기에는 좋은 문제였다 DFS의 경우 자신과 연결된 자식들중 하나에게로 간다음 계속 쭉 갔다가 자신의 부모로 돌아오는 게 핵심이다 DFS의 자식들이 오름차순으로 정렬 되어 있을수도 있고 내림차순으로 정렬 되어있을 수도 있다. 이전 문제는 오름차순으로 정렬해놓고 시작했다면 이번 문제에서는 내림차순으로 정렬하여 큰수 부터 방문하도록 하였다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> vertex[100001];
int visited[100001];
int visitedRank[100001];
int countnum=0;
void dfs(int start) {
	if (visited[start] == false) {
		visited[start] = true;
		countnum += 1;
		visitedRank[start] = countnum;
		int sizeofvertex = vertex[start].size();
		for (int i = 0; i < sizeofvertex; i++) {
			if (visited[vertex[start][i]] == false) {
				dfs(vertex[start][i]);
			}
		}
	}

}
int main() {
	int vertexnum, edgenum, startvertex;
	cin >> vertexnum >> edgenum >> startvertex;
	
	for (int i = 1; i <= edgenum; i++) {
		int temp1,temp2;
		cin >> temp1>>temp2;
		vertex[temp2].push_back(temp1);
		vertex[temp1].push_back(temp2);
	}
	for (int i = 1; i <= vertexnum; i++) {
		sort(vertex[i].rbegin(), vertex[i].rend());
	}
	dfs(startvertex);
	for (int i = 1; i <= vertexnum; i++) {
		cout << visitedRank[i] << '\n';
	}
}

자 코드를 한번 보자

내가 dfs에서 가장 좋아하는 방법은 vector로 선언하여 입력 받은 값들을 차례로 서로의 정점 번호를 index로 하는 vector에 서로서로를 넣는 방식이다 

for (int i = 1; i <= edgenum; i++) {
		int temp1,temp2;
		cin >> temp1>>temp2;
		vertex[temp2].push_back(temp1);
		vertex[temp1].push_back(temp2);
	}

그래서 이부분의 코드가 이렇게 되는 것이다 입력을 받았으면 지금 두정점이 연결된것이기 때문에 자기로 부터 연결되는 vector를 모두 넣어야하기 때문에 1-2 이렇게 연결되어있다면 2번 vertex 에는 1을 1번 vertex에는 2를 넣어 준다 그후 코드는 vector를 내림차순으로 정렬해준것이다 원래 벡터를 오름 차순으로 정렬할때는 vertex.begin과 vertex.end를 쓰지만 내림차순으로 정렬할 때는 rbegin과 rend를 써주면 내림 차순으로 정렬 한다 

void dfs(int start) {
	if (visited[start] == false) {
		visited[start] = true;
		countnum += 1;
		visitedRank[start] = countnum;
		int sizeofvertex = vertex[start].size();
		for (int i = 0; i < sizeofvertex; i++) {
			if (visited[vertex[start][i]] == false) {
				dfs(vertex[start][i]);
			}
		}
	}

}

그후 dfs코드는 이전에 첨부한 다른 문제와 비슷하다 일단 내가 방분하려고 하는 점이 방문된적이 없다면 그점을 방문했다고 true로 마크하고 방문한 번째수를 1증가시키고 해당정점의 등수를visitedRank에 표시해준다 그다음 그정점의 자식들 즉 vector에 있는 값들을 순회하면서 방문하지 않았던 좌표에 방문 한다.