[SW Expert] #2814 최장 경로

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

최장, 최단 자주 사용했던 dfs를 이용하여 해결하면 될것이라고 생각했으나 기존 2차원 배열을 활용하던 방법과 달리 그래프를 어떤 방식으로 해결해야하는지에 대한 에러사항이 생김. 공부를 통해 방법을 찾았고 첫번째 방법은 기존 방법과 비슷하게 이차원 배열에, 두번째 방법은 vector를 활용하여 연결리스트 형태로 구현하는 방식이다. 문제의 그래프는 무방향 그래프 이므로 다음과 같이 구현했다

---

2. 코드

#include<iostream>
#include<string.h>
#include<vector>

using namespace std;
int T;
int N;
int M;
int MAX;

bool check[20];

void dfs(int now, int length, vector<int> *value) {
	if (length > MAX) {
		MAX = length;
	}

	check[now] = true;

	for (int i = 0; i < value[now].size(); i++) {
		int next = value[now][i];
		if (check[next]) continue;
		else {
			dfs(next, length + 1, value);
		}
	}

	check[now] = false;
}

int main(int argc, char** argv)
{
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N >> M;

		vector<int> v[20];
		for (int j = 0; j < M; j++) {
			int x;
			int y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		MAX = 0;
		for (int k = 1; k <= N; k++) {
			memset(check, false, sizeof(check));
			dfs(k, 1, v);
		}

		cout << "#" << i+1 <<" " <<MAX << endl;
	}
}