이번에는 Tree 문제를 풀어보았습니다.
문제를 처음 봤을 때 트리의 조건만 만족하는지 확인하면 되는 문제라고 생각했습니다.
트리는 다음 두 가지 조건을 만족합니다.
- 간선의 개수가
정점의 개수 - 1개이다. - 모든 정점이 하나의 연결 요소로 이루어져 있다.
이를 이용하여 DFS로 연결 여부를 확인하도록 구현하였습니다.
문제 설명
여러 개의 그래프가 주어집니다.
각 그래프가 트리라면 "tree"를, 아니라면 "graph"를 출력해야 합니다.
풀이 아이디어
V1
처음에는 DFS를 수행하면서 이미 방문한 정점을 다시 방문하는 경우 사이클이 존재한다고 판단하도록 구현하였습니다.
DFS가 끝난 뒤에는 모든 정점이 방문되었는지도 확인하여 연결 여부를 검사하였습니다.
V2
다시 생각해보니 간선의 개수가 N-1이 아니라면 이미 트리가 될 수 없다는 점을 먼저 확인할 수 있었습니다.
또한 간선의 개수가 N-1인 그래프에서는 연결 요소가 하나인지 확인하기만 해도 트리 여부를 판단할 수 있었습니다.
그래서 DFS는 단순히 연결 요소를 세는 용도로만 사용하도록 수정하였습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int visited[10][1001];
vector<vector<vector<int>>> injs;
vector<bool> isTree;
int N;
bool dfs(int here, int num, int prev) {
visited[num][here] = 1;
for (int next : injs[num][here]) {
if (next == prev) continue;
if (visited[num][next])
return false;
if (!dfs(next, num, here))
return false;
}
return true;
}
int main() {
cin >> N;
injs.resize(N,vector<vector<int>>());
isTree.resize(N);
for (int i = 0; i < N; i++) {
int nodes;
int inp_num;
bool tree_flag = true;
cin >> nodes;
cin >> inp_num;
injs[i].resize(nodes+1);
if (inp_num != nodes-1)
tree_flag = false;
for (int j=0; j<inp_num; j++) {
int a,b;
cin >> a >> b;
injs[i][a].push_back(b);
injs[i][b].push_back(a);
}
if (tree_flag && !dfs(1, i, 0))
tree_flag = false;
for (int j=1; j<=nodes; j++) {
if (!visited[i][j]) {
tree_flag = false;
break;
}
}
isTree[i] = tree_flag;
}
for (int i = 0; i < N; i++) {
if (isTree[i])
cout << "tree" << '\n';
else
cout << "graph" << '\n';
}
return 0;
}V1 풀이 흐름
- 그래프를 입력받습니다.
- 간선의 개수가
N-1인지 확인합니다. - DFS를 수행합니다.
- 이미 방문한 정점을 다시 방문하면 트리가 아니라고 판단합니다.
- DFS가 끝난 뒤 모든 정점이 방문되었는지 확인합니다.
- 결과를 출력합니다.
V1 구현 포인트
1. 사이클 확인
DFS를 수행하면서 이전 정점을 제외한 이미 방문한 정점을 만나면 사이클이 존재하는 것입니다.
if (next == prev) continue;
if (visited[num][next])
return false;트리에서는 이러한 경우가 발생하면 안 됩니다.
2. 연결 여부 확인
DFS가 끝난 뒤 방문하지 않은 정점이 있는지 확인하였습니다.
for (int j=1; j<=nodes; j++) {
if (!visited[i][j]) {
tree_flag = false;
break;
}
}방문하지 않은 정점이 존재한다면 연결 그래프가 아니므로 트리가 될 수 없습니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int N,visited[1001];
vector<vector<int>> inj;
vector<bool> ret;
void dfs(int here) {
visited[here] = 1;
for (int next : inj[here]) {
if (!visited[next])
dfs(next);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
memset(visited, 0, sizeof(visited));
int nodes;
int inp_num;
cin >> nodes >> inp_num;
inj.clear();
inj.resize(nodes + 1);
for (int j = 0; j < inp_num; j++) {
int a, b;
cin >> a >> b;
inj[a].push_back(b);
inj[b].push_back(a);
}
if (inp_num != nodes - 1) {
ret.push_back(false);
continue;
}
int cnt = 0;
for (int j = 1; j <= nodes; j++) {
if (!visited[j]) {
dfs(j);
cnt++;
}
}
if (cnt != 1) {
ret.push_back(false);
continue;
}
ret.push_back(true);
}
for (int i = 0; i < N; i++) {
if (ret[i])
cout << "tree\n";
else
cout << "graph\n";
}
}V2 풀이 흐름
- 그래프를 입력받습니다.
- 간선의 개수가
N-1인지 확인합니다. - DFS를 수행하여 연결 요소의 개수를 계산합니다.
- 연결 요소가 하나라면 트리입니다.
- 그렇지 않다면 그래프로 판단합니다.
V2 구현 포인트
1. 간선 개수 먼저 확인
트리는 반드시 간선의 개수가 정점 개수 - 1이어야 합니다.
if (inp_num != nodes - 1) {
ret.push_back(false);
continue;
}조건을 만족하지 않으면 DFS를 수행할 필요가 없습니다.
2. 연결 요소 개수 계산
DFS를 수행한 횟수를 이용하여 연결 요소의 개수를 구하였습니다.
int cnt = 0;
for (int j = 1; j <= nodes; j++) {
if (!visited[j]) {
dfs(j);
cnt++;
}
}DFS가 한 번만 수행되었다면 모든 정점이 연결되어 있다는 의미입니다.
3. 트리 여부 판단
연결 요소가 하나라면 트리로 판단하였습니다.
if (cnt != 1) {
ret.push_back(false);
continue;
}간선의 개수가 N-1이고 연결 요소가 하나라면 트리의 조건을 모두 만족하게 됩니다.
V2가 V1보다 코드가 훨씬 단순합니다.
V1에서는 사이클 검사와 연결 여부를 각각 확인했지만, V2에서는 간선 수가 N-1이라는 조건을 먼저 이용하여 DFS는 연결 요소 개수만 확인하도록 단순화한 것이 핵심입니다.
