[그래프] 인접 리스트

설명설명

[ BFS, DFS 구현(인접리스트 활용) ]

DFS와 BFS 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 42846 13356 8023 29.497% 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 예제 입력 1  4 5 1 1 2 1 3 1 4 2 4 3 4 예제 출력 1  1 2 4 3 1 2 3 4

#include <stdio.h>
#define MAX_EDGE_SIZE 1002
#define MAX_VERTEX_SIZE 20002

template<typename T>
class Queue
{
public:
	int front = 0;
	int rear = 0;
	T data[MAX_VERTEX_SIZE] = { 0, };
	
	Queue() {}

	void push(T d)
	{
		data[rear] = d;
		rear = (rear + 1) % MAX_VERTEX_SIZE;
	}

	T pop(void)
	{
		int result = data[front];
		front = (front + 1) % MAX_VERTEX_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }
};

class Edge
{
public:
	int from;
	int to;

	Edge() { from = to = 0; }
	Edge(int f, int t) : from(f), to(t) {}

	bool operator <= (Edge other)
	{
		if (from == other.from) return to <= other.to;
		else return from <= other.from;
	}
};

class Graph
{
public:
	int M;
	int N;
	int cnt[MAX_EDGE_SIZE] = { 0, };
	bool visited[MAX_EDGE_SIZE] = { 0, };
	Edge edge[MAX_VERTEX_SIZE];

	Graph() {}

	void initVisited()
	{
		for (register int i = 0; i <= N; i++) visited[i] = 0;
	}

	void updateGraph()
	{
		M *= 2;
		mergeSort(0, M - 1);

		for (register int i = 0; i < M; i++) cnt[edge[i].from] += 1;
		for (register int i = 1; i <= N; i++) cnt[i] += cnt[i - 1];
	}

	void DFS(int node)
	{
		visited[node] = true;
		printf("%d ", node);

		for (int i = cnt[node - 1]; i < cnt[node]; i++)
		{
			int nextNode = edge[i].to;

			if (visited[nextNode] == false)
				DFS(nextNode);
		}
	}

	void BFS(int start)
	{
		Queue<int> q;

		q.push(start);
		printf("%d ", start);
		visited[start] = true;

		while (!q.isEmpty())
		{
			int nowNode = q.pop();

			for (register int i = cnt[nowNode - 1]; i < cnt[nowNode]; i++)
			{
				int nextNode = edge[i].to;

				if (visited[nextNode] == false)
				{
					q.push(nextNode);
					printf("%d ", nextNode);
					visited[nextNode] = true;
				}
			}
		}
	}

private:
	Edge tempEdge[MAX_VERTEX_SIZE];

	void mergeSort(int start, int end)
	{
		if (start == end) return;
		int mid = (start + end) / 2;

		mergeSort(start, mid);
		mergeSort(mid + 1, end);
		merge(start, end);
	}

	void merge(int start, int end)
	{
		int i = start;
		int mid = (start + end) / 2;
		int j = mid + 1;
		int k = 0;

		while (i <= mid && j <= end)
		{
			if (edge[i] <= edge[j]) tempEdge[k++] = edge[i++];
			else tempEdge[k++] = edge[j++];
		}

		while (i <= mid) tempEdge[k++] = edge[i++];
		while (j <= end) tempEdge[k++] = edge[j++];

		for (i = start; i <= end; i++)
			edge[i] = tempEdge[i - start];
	}
};

int main(void)
{
	int start;
	Graph g;

	scanf("%d %d %d", &g.N, &g.M, &start);

	for (register int i = 0; i < g.M; i++)
	{
		scanf("%d %d", &g.edge[i].from, &g.edge[i].to);
		g.edge[i + g.M].to = g.edge[i].from;
		g.edge[i + g.M].from = g.edge[i].to;
	}
	g.updateGraph();

	g.DFS(start);
	g.initVisited();
	printf("\n");
	g.BFS(start);

	return 0;
}