백준 C++ 27779번) DFS 깊이 우선 탐색

사용언어 : C++

 

자료구조 공부 및 알고리즘 공부를 위해서 27779번 문제를 풀어보았습니다.

여기서 저도 인접행렬을 통해서 문제를 풀어보려고 했으나, 배열 크기가 너무 커서 아예 생성조차 되지 않았습니다. 그래서 두번째로, 인접리스트를 공부하여 풀어보았습니다.

 

DFS 자체는 깊이 우선탐색이기 때문에 하나를 깊게 들어간 후 백트래킹을 통해서 안간 곳이 있나 확인하면서 나오는 알고리즘입니다.

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

using namespace std;
#define MAXR 100001

vector<int> arr[MAXR];
vector<int> visit(MAXR, 0);
int coun;

void DFS(int start);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, R;

	cin >> N >> M >> R;

	for (int i = 0; i < M; ++i) {
		int u, v;
		cin >> u >> v;
		arr[u].push_back(v);
		arr[v].push_back(u);
	}
	for (int i = 1; i <= N; i++) {
		sort(arr[i].begin(), arr[i].end());
	}

	DFS(R);

	for (int i = 1; i <= N; i++) {
		cout << visit[i] << "\n";
	}
}
void DFS(int start) {
	visit[start] = ++coun;

	for (auto& edge : arr[start]) {

		if (visit[edge])
			continue;

		DFS(edge);
	}
}

여기서 마지막으로 삽질했던 것이 "\n" 대신에 endl을 썻었는데 저거 하나 때문에 계속 시간초과 오류가 떳습니다. 하.. 거의 30분을 봤는데 저거 하나때문이였다니.,. 진짜 너무하네요..