[C++] 백준 1260번: DFS와 BFS

1260번: DFS와 BFS

문제 바로가기

이 문제를 풀기 전에는 DFS, BFS에 대해서 아는 것이 거의 없었다.

유튜브 강의 여럿을 참고했는데, 다음 영상이 도움이 많이 됐다.

 

 

나는 위 영상에서 처럼 클래스를 생성해서 이 문제를 풀기로 다짐했다.

Node 클래스와, Graph 클래스를 정의했다.

모든 멤버들은 public으로 선언하여 외부에서 자유롭게 접근할 수 있도록 했다.

Node에는 출력했음을 기록하는 mark, Node의 번호를 나타내는 number, 간선의 갯수인 relations를 선언했다.

간선을 저장하는 lines에는 대상이 되는 Node의 주솟값을 저장했다.

Graph에는 저장하고 있는 Node의 갯수와 Node의 배열을 선언했다.

class Node {
public:
	bool mark;
	int number;
	int relations;
	vector<Node*> lines;
};

class Graph {
public:
	int size;
	Node* nodes;
};

각 클래스에 대한 생성자도 정의해줬다.

복사생성자에서는 배열에 대해 깊은 복사를 해줬다.

class Node {
public:
	bool mark;
	int number;
	int relations;
	vector<Node*> lines;

	/* Constructors */
	Node() : mark(false), number(0), relations(0) { }

	Node(const Node& other) : mark(false), number(other.number), relations(other.relations) {
		lines.resize(other.lines.size());
		copy(other.lines.begin(), other.lines.end(), lines.begin());
	}
};

class Graph {
public:
	int size;
	Node* nodes;

	/* Constructors */
	Graph() : size(0), nodes(nullptr) { }

	Graph(int size) : size(size) {
		nodes = new Node[size];
		for (int i = 0; i < size; i++)
			nodes[i].number = i + 1;
	}

	Graph(Graph& other) : size(other.size) {
		nodes = new Node[other.size];
		for (int i = 0; i < other.size; i++)
			nodes[i] = other.nodes[i];
	}
};

main 함수 설계는 다음과 같이 했다.

1. 그래프와 노드, 각 간선을 만든다
2. 각 노드의 간선을 내림차순으로 정렬한다
3. DFS 수행(stack)
4. 노드의 mark 표시를 초기화 한 후 각 노드의 간선을 오름차순으로 정렬한다
5. BFS 수행(queue)

위에서 간선을 정렬한 다는 것은, 각 노드에서 다른 노드로 향할 때 해당 노드의 번호에 따라서 정렬한다는 것이다.

예제 1에서 1번 Node의 간선은 2번, 3번, 4번 순서대로 Vector에 담기게 되는데 이 순서를 내림차순으로 정렬하면,

4번, 3번, 2번 순서로 바뀌는 것이다.

이렇게 정렬함으로써 stack을 이용해 DFS를 수행할 때, 번호가 작은 Node부터 출력하게 된다.

전체 코드는 아래와 같다.

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

class Node {
public:
	bool mark;
	int number;
	int relations;
	vector<Node*> lines;

	/* Constructors */
	Node() : mark(false), number(0), relations(0) { }

	Node(const Node& other) : mark(false), number(other.number), relations(other.relations) {
		lines.resize(other.lines.size());
		copy(other.lines.begin(), other.lines.end(), lines.begin());
	}

	/* Destructor */
	~Node() {
		lines.clear();
	}

	/* Member Functions */
	void addLine(Node* node) {
		if (find(lines.begin(), lines.end(), node) != lines.end())
			return;
		lines.push_back(node);
		relations++;
	}

	void sortLinesGreater() {
		if (lines.size() == 0)
			return;
		vector<Node*> temp;
		while (lines.size()) {
			auto max = lines.begin();
			for (auto iter = lines.begin(); iter != lines.end(); ++iter)
				if ((*iter)->number >= (*max)->number)
					max = iter;
			temp.push_back(*max);
			lines.erase(max);
		}
		swap(lines, temp);
	}

	void sortLinesLess() {
		if (lines.size() == 0)
			return;
		vector<Node*> temp;
		while (lines.size()) {
			auto min = lines.begin();
			for (auto iter = lines.begin(); iter != lines.end(); ++iter)
				if ((*iter)->number <= (*min)->number)
					min = iter;
			temp.push_back(*min);
			lines.erase(min);
		}
		swap(lines, temp);
	}
};

class Graph {
public:
	int size;
	Node* nodes;

	/* Constructors */
	Graph() : size(0), nodes(nullptr) { }

	Graph(int size) : size(size) {
		nodes = new Node[size];
		for (int i = 0; i < size; i++)
			nodes[i].number = i + 1;
	}

	Graph(Graph& other) : size(other.size) {
		nodes = new Node[other.size];
		for (int i = 0; i < other.size; i++)
			nodes[i] = other.nodes[i];
	}

	/* Member Functions */
	void addLine(int node_1, int node_2) {
		nodes[node_1 - 1].addLine(&nodes[node_2 - 1]);
		nodes[node_2 - 1].addLine(&nodes[node_1 - 1]);
	}
};

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

	// Create Graph and Lines
	Graph graph(N);
	for (int i = 0; i < M; i++) {
		int nodes[2];
		scanf("%d %d", nodes, nodes + 1);
		graph.addLine(nodes[0], nodes[1]);
	}

	// Sort Each Lines of Nodes (greater)
	for (int i = 0; i < graph.size; i++)
		graph.nodes[i].sortLinesGreater();

	// DFS
	stack<Node*> DFS;
	DFS.push(&graph.nodes[V - 1]);
	while (DFS.size()) {
		while (DFS.top()->mark) {
			DFS.pop();
			if (DFS.size() == 0)
				goto OUT_1;
		}
		Node& now = *DFS.top();
		DFS.pop();
		for (auto iter = now.lines.begin(); iter != now.lines.end(); ++iter)
			if (!now.mark)
				DFS.push(*iter);
		printf("%d ", now.number);
		now.mark = true;
	}
OUT_1:
	printf("\n");

	// Initialize Nodes' Mark & Sort Each Its Lines (Less)
	for (int i = 0; i < graph.size; i++) {
		graph.nodes[i].mark = false;
		graph.nodes[i].sortLinesLess();
	}


	// BFS
	queue<Node*> BFS;
	BFS.push(&graph.nodes[V - 1]);
	while (BFS.size()) {
		while (BFS.front()->mark) {
			BFS.pop();
			if (BFS.size() == 0)
				goto OUT_2;
		}
		Node& now = *BFS.front();
		BFS.pop();
		for (auto iter = now.lines.begin(); iter != now.lines.end(); ++iter)
			if (!now.mark)
				BFS.push(*iter);
		printf("%d ", now.number);
		now.mark = true;
	}
OUT_2:
	printf("\n");

	return 0;
}