[백준(BOJ)]24479 - 알고리즘 수업 - 깊이 우선 탐색1 (C/C++)

백준 24479번 DFS문제. 단계 그래프와 순회에 위치해 있다.

틀린 것 보다는 런타임 에러가 많이 났다. 세그멘테이션 폴트....^^;

우선 이번엔 시간초과 보다는 런타임 에러가 많이 떳다. 범위 오류와 Segmentation fault ㅎㅎ;

문제 자체를 잘못 이해하여 방문하는 순서를 적는 줄 알았는데, 알고보니 순서대로 i번째 정점이 몇 번째로 출력되는질 적는 것 이였다... 이걸 이해못해서 틀린게 세번

시간초과또한 두 번이나 나왔는데, 굳이 vector를 이용하여 find를 사용해 풀었기 때문에 시간복잡도가 O(N)이 나와버려 시간이 오바되버렸다... 그냥 visited를 int로 바꿔줬으면 되는걸

아무튼 짜잘한 문제를 전부 해결 하고 나니 성공!

이번에도 시간을 줄이기 위하여 ios_base를 사용하였다.

 

해당 문제는 DFS를 활용하는 문제이다. DFS가 아니면 어캐풀지? 란 느낌의 정석 DFS문제였다.

DFS는 깊이 우선 탐색(Depth First Search)라고 하며 그래프를 탐색하는 방법 중 하나이다.

약간 Tree구조에서 시작 노드에서 탐색하는? 그런 느낌이라고 보면 된다. 대신 방향성이 없는 ㅇㅇ 아님말고

다른 블로그는 막 그림그리고 설명하고 이러는데 그림까지 그릴 깜냥은 안되서 그냥 이정도만 설명하겠다.

어차피 나무위키가면 친절하게 설명해주니까 이왕 볼거면 인접행렬,인접리스트 정도까지 보고가도 좋을 것 같다.

 

내가 생각하기에 DFS, BFS는 알고리즘의 시작이 아닐까 생각한다. 쉬우면서도 생각을 많이하게 한다.

다른 나무위키나 블로그에서 안보고 백준 수도코드만을 가지고 공부했는데, 하루반? 이틀정도 걸린 것 같다.

2학년이후로 졸작에 집중해서 그런가 다 까먹은 듯 ㅎㅎ;

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

using namespace std;


int* visited; // [100001] {};
int cnt{0};
vector<int> OrderNum;
vector<int>* isGraph;
void Visit(int n, int m, int r);

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int n, m, r; // n:정점의 수, m:간선의 수, r:시작 정점
	cin >> n >> m >> r;

	visited = new int[n + 1]{0,};

	isGraph = new vector<int>[n+1];
	for (int i =0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		//isGraph[a].push_back(b);
		isGraph[a].emplace_back(b);
		isGraph[b].emplace_back(a);
	}

	for (int i = 0; i < n+1; ++i)
	{
		if(isGraph[i].size() > 0)
		sort(isGraph[i].begin(), isGraph[i].end());
	}

	Visit(n, m, r);
	/*for (int i = 1; i < n + 1; ++i)
	{
		auto Num = find(OrderNum.begin(), OrderNum.end(), i);
		if (Num == OrderNum.end())
		{
			cout << 0 << "\n";
		}
		else
		{
			cout << Num - OrderNum.begin()+1 << "\n";
		}
	}*/
	for (int i = 1; i < n + 1; ++i)
	{
		cout << visited[i] << "\n";
	}
}

void Visit(int n, int m, int r)
{
	visited[r] = ++cnt;
	
	for (int i = 0; i < isGraph[r].size(); ++i)
	{
		int y = isGraph[r][i];
		if (0 == visited[y]) Visit(n, m, isGraph[r][i]);
	}
	
}

중간에 보이는 OrderNum Vector때문에 시간초과가 두번이나 났다;; O(1)로 끝낼걸 O(N)으로 하니까 틀릴 수 밖에..

아무튼 중요하게 봐야할 코드는 아래 void Visit이라고 생각한다. 저렇게 재귀적으로 함수를 호출해야한다.

또한, DFS는 무방향성 그래프이기 때문에, a - b 라고 한다면, (a,b) (b,a)가 같아야 한다. 따라서, 간선 정보를 입력받은 뒤, emplace_back을 a와 b 모두 해주었다. 그래야만 다른 정점에서도 정보가 같이 들어가기 때문이다.

또한, 오름차순으로 움직여야 하기 때문에, 모든 정보를 받은 뒤, sort를 해주었다. sort를 해주지 않으면, 먼저 들어온 순서대로 움직이기 때문

 

다음 문제는 DFS관련 문제를 하나 더 푼 뒤, BFS문제를 업로드할 생각이다.

이로서 내 106번째 문제 해결

목표까지는 대충 50문제..!