[Baekjoon] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

---

 

문제 해결 과정

착안

간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 깊이 우선 탐색 알고리즘을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 깊이 우선 탐색(depth-first search, DFS) 알고리즘을 구현하였다. 이때, 한 정점에 대한 간선의 순서를 '인접한 정점을 오름차순으로 방문하는 순서'가 되도록 정렬하는 것을 문제에서 요구하였기 때문에 연결 리스트(linked list)를 기반으로 하는 그래프 구조보다는, 정점의 목록을 배열 형태로 가지어 정점의 번호에 따라 접근하기가 편리하도록 그래프 구조를 구현하는 것이 좋을 것 같아서 STL의 vector 클래스를 활용하여 그래프를 구현해보았다.

 

간선의 정렬에 있어서는, 문제에서 별도로 제한한 조건이 없었기 때문에 STL의 algorithm 헤더에 포함되어있는 sort() 함수를 사용하여 인접한 정점을 오름차순으로 방문할 수 있는 순서로 간선을 정렬하고자 하였다.

 

구현

무방향 그래프이므로 간선이 주어지면 양방향으로 모두 연결하는 점에 주의하여 구현하였다. 그래프 자료 구조에서의 순회를 수행하므로 정점의 방문 여부를 표시해야했는데, 이때 문제에서 정점의 방문 순서를 출력하는 것을 요구했기 때문에 추가적으로 정점의 방문 순서를 저장함과 동시에 방문 여부를 표시할 수 있으므로(0이 아닌 경우에는 방문한 정점임) 두 가지 정보를 하나의 변수로 표현하도록 구현하였다(아래 코드에서 Graph::Vertex::VisitOrder 멤버).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Graph
{
	struct Vertex
	{
		vector<int> NextIndex;
		int VisitOrder = 0;
	};

	Graph(int N)
	{
		V = vector<Vertex>(N);
	}

	void AddEdge(int From, int Dest)
	{
		V[From - 1].NextIndex.push_back(Dest);
	}

	void SortEdge()
	{
		for (Vertex& v : V)
			sort(v.NextIndex.begin(), v.NextIndex.end());
	}

	void DFS(int index)
	{
		Vertex& currV = V[index - 1];
		currV.VisitOrder = Order++;
		for (int index : currV.NextIndex)
		{
			if (!V[index - 1].VisitOrder)
				DFS(index);
		}
	}

	vector<Vertex> V;
	int Order = 1;
};


int main()
{
	int N, M, R;
	scanf("%d %d %d", &N, &M, &R);

	Graph graph = Graph(N);

	int from, dest;
	while (M--)
	{
		scanf("%d %d", &from, &dest);
		graph.AddEdge(from, dest);
		graph.AddEdge(dest, from);
	}

	graph.SortEdge();
	graph.DFS(R);

	for (Graph::Vertex v : graph.V)
		printf("%d\n", v.VisitOrder);

	return 0;
}

 

실행 결과