[swea] 2814 최장경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

 

1. 거리를 구하는 문제라 bfs를 떠올리고 사용

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define FAST cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
using namespace std;

int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {

		// 그래프 상에서 최장 경로의 길이 -> 모든 정점에서 bfs를 돌려야함.

		int n, m;
		cin >> n >> m;
		vector<vector<int>> graph(n+1);

		for (int i = 0; i < m; i++) {
			int x; int y;
			cin >> x >> y;
			graph[x].push_back(y);
			graph[y].push_back(x);
		}
		int maxx = 1;
		vector<int> isvisited(n+1, 0);

		// 모든 정점에 대해서 bfs를 진행하기 -> cnt도 같이 넣어서 주기
		// bfs를 진행하는 방법은 graph[x]에 있는 모든 간선 정보에 대해서 진행

		queue<pair<int, int>> q; // 정점 번호, cnt
		
		for (int i = 1; i <= n; i++) {
			fill(isvisited.begin(), isvisited.end(), 0);
			q.push({ i ,1 });
			isvisited[i] = 1;
			while (!q.empty()) {

				bool flag = false;
				int x = q.front().first;
				int ccnt = q.front().second;
				//cout << x << " " << ccnt << endl;
				q.pop();

				for (int j = 0; j < graph[x].size(); j++) {

					if (isvisited[graph[x][j]] == 1) continue;

					q.push({ graph[x][j], ccnt + 1 });
					isvisited[graph[x][j]] = 1;
					flag = true;
				}

				if (flag == false) maxx = max(maxx, ccnt);
				// 더이상 갈곳이 없을때 maxx 갱신해주기
			}

		}

		cout << "#" << tc << " " << maxx << '\n';
	}
	return 0;
}

bfs를 사용할 시에 cycle이 존재하는 경우 최장거리를 구할 수 없음.

따라서 dfs를 사용해야함.

 

2. 정점마다 dfs 시작해주는 코드(시간초과)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


vector<vector<int>> graph(11);
int isvisited[11];
int maxx = 1;

void dfs(int vertex, int cnt) {

	for (int i = 0; i < graph[vertex].size(); i++) {

		if (isvisited[graph[vertex][i]] == 1) continue;

		isvisited[graph[vertex][i]] = 1;
		dfs(graph[vertex][i], cnt + 1);
		isvisited[graph[vertex][i]] = 0;
	}
	maxx = max(maxx, cnt);
}
// maxx 값은 언제 갱신해주지? -> 더이상 dfs로 갈 곳이 없는 경우 -> for문이 끝난 후?

int main() {

	int t;
	cin >> t;

	for (int tc = 1; tc <= t; tc++) {

		int n, m;
		cin >> n >> m;

		for (int i = 1; i <= m; i++) {
			int from; int to;
			cin >> from >> to;

			graph[from].push_back(to);
			graph[to].push_back(from);
		}


		for (int i = 1; i <= n; i++) {
			isvisited[i] = 1;
			dfs(i, 1); // 정점 정보와 cnt
			isvisited[i] = 0;
		}

		cout << "#" << tc << " " << maxx << '\n';
	}
}

모든 정점에 대해서 dfs를 수행. 시간초과

최악의 경우 O(n+e)를 n번 반복 -> O(n(n+e))

n은 최대 10개 e는 최대 20개

테스트 케이스당 0.1초로 수행하면 가능

 

이론상 시간복잡도에는 걸리지 않는것 같았다.

문제는 테스트케이스 마다 graph를 초기화 해줘야 하는데 graph를 초기화해주지 않아서 였다.

따라서 graph의 정점마다 간선 정보가 계속 쌓이게되고 틀린답은 물론 계속해서 간선이 추가되니 시간이 점점 길어지는 것을 볼 수 있다. 최악의 경우에는 간선 정보가 20개씩 쌓이면서 10번째 테스트케이스에서는 200개가 쌓일 수 있다.

-> 그래서 graph를 계속 초기화해주면 문제가 해결된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;


vector<vector<int>> graph(11);
int isvisited[11];
int maxx = 1;

void dfs(int vertex, int cnt) {

	for (int i = 0; i < graph[vertex].size(); i++) {

		if (isvisited[graph[vertex][i]] == 1) continue;

		isvisited[graph[vertex][i]] = 1;
		dfs(graph[vertex][i], cnt + 1);
		isvisited[graph[vertex][i]] = 0;
	}
	maxx = max(maxx, cnt);
}
// maxx 값은 언제 갱신해주지? -> 더이상 dfs로 갈 곳이 없는 경우 -> for문이 끝난 후?

int main() {

	int t;
	cin >> t;

	for (int tc = 1; tc <= t; tc++) {

		int n, m;
		cin >> n >> m;
		memset(isvisited, 0, sizeof(isvisited));
		for (int i = 0; i < 11; i++) {
			graph[i].clear();
		}
		maxx = -1;

		for (int i = 1; i <= m; i++) {
			int from; int to;
			cin >> from >> to;

			graph[from].push_back(to);
			graph[to].push_back(from);
		}


		for (int i = 1; i <= n; i++) {
			isvisited[i] = 1;
			dfs(i, 1); // 정점 정보와 cnt
			isvisited[i] = 0;
		}

		cout << "#" << tc << " " << maxx << '\n';
	}
}