DFS 문제

예제문제

예제문제4

문제소개

예제 문제 4 (DFS)
수거 로봇을 이용해 쓰레기를 수거합니다.
쓰레기 로봇이 충전할 수 있는 정착장이 하나 있습니다. (수정필요)
쓰레기와 쓰레기, 정착장과 쓰레기 거리는 모두 1KM로 동일합니다.
물살로 인해 역방향 운항을 불가합니다.
9번쓰레기를 수거하러 가는 도중 신호가 끊겼습니다. 수거 로봇이 이동하고 있는 모든 경로를 나열하여, 수거 로봇의 위치를 특정하세요.
정착장 : 0
쓰레기 : 정착장을 제외한 모든 노드
화살표있음 (수정 필요-완료)
v={0,1,2,3,4,5,6,7,8,9}
E={(0,1),(0,2),(1,2),(1,3),(1,4}),(2,3),(3,4),(4,5),(4,6),(4,7),(5,9),(6,7),(7,5),(7,8),(8,5)}

문제풀이

문제코드

#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;

class CGraph {
	int n_vertices;
	bool* visited;
	int* paths; //예제문제 4번 추가부분
	vector<list<int>> adj; //간선
	vector<int> dist; //정점간 얼마나 떨어져 있는지

public:
	CGraph(int _n) {
		this->n_vertices = _n;
		visited = new bool[_n];
		for (int i = 0; i < _n; ++i) { //생성자 초기화
			visited[i] = false;
			paths[i] = false;  //path 초기화 필요
			
		}
		adj.resize(_n);
		dist.resize(_n);
	}
	~CGraph() {
		delete visited;
	}

	//방향이 없을 때
	void addUndirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
		adj[_d].push_back(_s);
	}
	//방향을 넣어주고 싶을때
	void addDirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
	}
	//DFS알고리즘 (순환)
	void DFS(int _s) {
		visited[_s] = true; //시작점을 방문한다.
		cout << _s << " ";
		//이터레이터 사용
		//같은 컨테이너에 저장되어 있는 원소를 참조
		list<int>::iterator iter;
		for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter) {// 이터레이터 사용, 모든 원소를 본다.
			if (!visited[*iter]) { //포인터로 표현해주어야 한다
				visited[*iter] = true;
				DFS(*iter);
			}
			for (int i = 0; i < n_vertices; ++i) {		// 저장한 거리들을 확인해 봅니다. 콘솔창에 간략히 출력할게요.
				cout << i << " : " << dist[i] << endl;
			}
		}
	}

	//예제문제4 추가 코드
	void DFS_2(int _s, int _d, int _idx) {
		visited[_s] = true;
		paths[_idx++] = _s;
		if (_s == _d) {
			for (int i = 0; i < _idx; +i) {
				cout << paths[i];
			}
			cout << endl;
		}
		else {
			list<int>::iterator iter;
			for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter) {// 이터레이터 사용, 모든 원소를 본다.
				if (!visited[*iter]) { //포인터로 표현해주어야 한다
					DFS_2(*iter, _d, _idx);
				}

			}
		}
	}
};


int main() {
	CGraph OGraph(10);
	OGraph.addUndirectedEdge(0, 1);
	OGraph.addUndirectedEdge(0, 2);
	OGraph.addUndirectedEdge(1, 3);
	OGraph.addUndirectedEdge(1, 4);
	OGraph.addUndirectedEdge(2, 3);
	OGraph.addUndirectedEdge(3, 4);
	OGraph.addUndirectedEdge(4, 5);
	OGraph.addUndirectedEdge(4, 6);
	OGraph.addUndirectedEdge(4, 7);
	OGraph.addUndirectedEdge(5, 7);
	OGraph.addUndirectedEdge(5, 8);
	OGraph.addUndirectedEdge(5, 9);
	OGraph.addUndirectedEdge(6, 7);
	OGraph.addUndirectedEdge(7, 8);
	return 0;
}

인접행렬

인접 행렬(adjacency)

정점의 값 : char veritces[MAX_VTXS]
간선 정보(행렬을 사용한다.) : int adj[MAX_VTXS][MAX_VTXS]

인접 리스트(adjacency list)

각 정점..........이씨
adj[A] -> B -> C
정점에 연결된 간선 : List
adj[A] -> B -> C
adj[B] -> 공
adj[C] -> 공
모든 간선 정보 : vector

가중치

가중치 그래프

BFS(가중치O)

DFS(가중치O)

KRUSKAL

DIGKSTRA