[백준/BOJ] 백준 14953번 : Game Map

https://www.acmicpc.net/problem/14953

14953번: Game Map

 

연결된 간선의 개수가 작은 노드부터 자신의 노드보다 연결된 간선의 수가 더 많은 노드로만 탐색하는 dfs를 수행하여, max_pass에, max_pass[노드 번호] = "해당 노드부터 최대 이동할 수 있는 정점의 개수"를 저장하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;

int n, m;
vector<int> adj[100005];
vector<int> edge_cnt(100005, 0);
vector<int> max_pass(100005, 0);
vector<int> visited(100005, 0);

void dfs(int here) {
	visited[here] = 1;

	int here_max_pass = 1;
	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (edge_cnt[there] > edge_cnt[here]) {
			if (visited[there] == 0) {
				dfs(there);
			}

			here_max_pass = max(here_max_pass, 1 + max_pass[there]);
		}
	}

	max_pass[here] = here_max_pass;
}

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

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);

		edge_cnt[u]++;
		edge_cnt[v]++;
	}

	//연결된 간선의 개수가 작은 순으로 정렬
	vector<pair<int, int>> node;
	for (int i = 0; i < n; i++) {
		node.push_back(make_pair(edge_cnt[i], i));
	}
	sort(node.begin(), node.end());

	//연결된 간선의 개수가 작은것 부터 확인
	for (int i = 0; i < node.size(); i++) {
		int start = node[i].second;
		if (visited[start] == 0) {
			dfs(start);
		}
	}


	int result = 1;
	for (int i = 0; i < n; i++) {
		result = max(result, max_pass[i]);
	}
	cout << result;

	return 0;
}