문제

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

---

풀이

DFS

DFS 연산 결과, 여행가려는 도시들이 그래프 상에서 모두 연결되어 있으면 YES, 아니면 NO를 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 201; 
int N, M;
vector<int> graph[MAX]; 
bool visited[MAX]; 
vector<int> path;

void input() {
	cin >> N >> M;

	// 그래프 정보 저장
	for(int i = 1; i <= N; i++){ 
		for(int j = 1; j <= N; j++){
			int x; 
			cin >> x; 
			if(x == 1) graph[i].push_back(j);
		}
	}

	// 여행 계획에 속한 도시들의 경로 (M개) 
	for(int i = 0; i < M; i++){ 
		int city; 
		cin >> city; 
		path.push_back(city); 
	}
}

void dfs(int x){
	visited[x] = true;
	for(int i = 0; i < graph[x].size(); i++){
		int y = graph[x][i];
		if(!visited[y]){
			dfs(y); 
		}
	}
}

void solution() {
	int cnt = 0; // 연결 요소의 개수 
    
	for(auto city: path){ 
		// 모든 도시가 연결되어 있으면 cnt는 한번만 증가한다. 
		if(!visited[city]){
			cnt++;
			dfs(city);
		}
	}

	if(cnt == 1) cout << "YES\n";
	else cout << "NO\n";
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();

	solution(); 

	return 0; 
}

• V: 정점의 개수, E: 간선의 개수, M: 여행하려는 도시의 개수
• V는 최대 200
• 모든 정점이 연결되어 있다면 E는 최대 (V - 1)개
• M은 최대 1000

연결 리스트로 그래프를 구현하면 DFS 함수의 시간복잡도는 O(V + E)이므로

여행하려는 도시에 대한 그래프 상의 연결 요소의 개수를 구할 때의 시간복잡도는 O(M * (V + E))일 것이다.

유니온 파인드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 201; 
int N, M;
int parent[MAX]; 
vector<int> path; 

int findRootNode(int x){
	if(x == parent[x]) return x; 
	return parent[x] = findRootNode(parent[x]);
}

void unionSet(int a, int b){
	if(a < b) parent[b] = a; 
	else parent[a] = b; 
}

void input() {
	cin >> N >> M;

	for(int i = 1; i <= N; i++){
		parent[i] = i; 
	}

	// 그래프 정보 저장
	for(int i = 1; i <= N; i++){ 
		for(int j = 1; j <= N; j++){
			int x; 
			cin >> x; 

			// 연결된 노드는 같은 집합으로 합치기 
			if(x == 1){
				int ri = findRootNode(i); 
				int rj = findRootNode(j); 
				unionSet(ri, rj); 
			}
		}
	}

	// 여행 계획에 속한 도시들의 경로 (M개) 
	for(int i = 0; i < M; i++){ 
		int city; 
		cin >> city; 
		path.push_back(city); 
	}
}

void solution() {
	// 여행하려는 모든 도시들의 루트 노드가 같은지 검사
	int rootNode = findRootNode(path[0]);
	
	for(int i = 1; i < path.size(); i++){
		int temp = findRootNode(path[i]);

		if(rootNode != temp){
			cout << "NO\n";
			return; 
		}
	}

	cout << "YES\n"; 
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();

	solution(); 

	return 0; 
}

여행하려는 모든 도시 M개에 대해, 루트 노드가 같은지 검사하는 알고리즘의 시간복잡도는 O(M)이다.

플로이드-워셜

플로이드-워셜 알고리즘은 보통 모든 정점 간의 최단 거리를 DP로 구할 때 사용되는데, 이 문제처럼 모든 정점 간의 연결 관계를 파악할 때도 사용할 수 있다.

i에서 k로, k에서 j로 가는 경로가 있다면, i에서 j로 가는 경로도 있다.

위와 같은 논리를 삼중 for문을 이용해서 코드로 구현할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 201; 
int N, M; 
int graph[MAX][MAX]; 
vector<int> path; 

void input() {
	cin >> N >> M; 

	// 노드 간의 연결 관계 
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> graph[i][j];

			// 자기 자신으로 가는 경로는 항상 있음!! 
			if(i == j) graph[i][j] = 1; 
		}
	}

	// 여행 경로 
	for(int i = 0; i < M; i++){
		int x; 
		cin >> x; 
		path.push_back(x);
	}
}

void solution() {
	for(int k = 1; k <= N; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				if(graph[i][k] == 1 && graph[k][j] == 1){ 
					graph[i][j] = 1; 
				}
			}
		}
	}

	int start = path[0];
	for(int i = 1; i < path.size(); i++){
		int next = path[i];

		// 시작점에서 갈 수 있는 경로가 없는 경우 
		if(graph[start][next] == 0){ 
			cout << "NO\n"; 
			return; 
		}
	}

	// 시작점에서 모든 도시까지 갈 수 있는 경우 
	cout << "YES\n"; 
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();

	solution(); 
	
	return 0; 
}

시간복잡도는 O(N^3)이지만, N이 최대 200이므로 이 풀이도 통과된다! (다만, 3가지 방식 중에서는 제일 비효율적인 방법이긴 하다.)