https://www.acmicpc.net/problem/4803
4803：나무
“나무 없음”을 출력합니다.
입력으로 주어진 그래프에 트리가 없으면 “트리가 하나 있습니다.
” 하나 있으면 “T 나무의 숲.” 테스트 사례 번호와 함께 T(T > 1) 트리가 있는 경우. 하다.
www.acmicpc.net
문제 접근
첫 번째는 union & find로 해결되었습니다.
합체하는 과정에서 이미 합체를 하고 같은 트리에 있는데 한 번 더 시도하면 트리가 되지 않습니다.
트리에 하나 이상의 Edge가 생성되면 어떻게 연결되어 있든 관계없이 주기 형태로 만들어지기 때문에
이에 대해 생각하는 과정에서 찾기 경로를 압축해도 상관 없습니다.
나는 그것이 정보라는 것을 생각할 수도 있습니다.
union&find에서 사용할 부모가 순환이 아닌 경우 2차원 배열로 만들어서 False 처리하기로 했습니다.
그리고 문제에 표시된 모든 간선을 계산한 후, 거짓이 아님 루트 노드 수 = 트리 수다음과 같이 볼 수 있습니다.
합집합 및 찾기 알고리즘
합집합 및 찾기 알고리즘
Union & Find Union & Find라는 알고리즘은 Union과 Find로 구성됩니다.
Union is merging Find는 트리를 사용하여 두 세트가 동일한 세트에 있는지 확인하여 동일한 세트에 있는지 확인하는 방법입니다.
휴대용-종이.tistory.com
두 번째는 DFS로 해결했습니다.
사실 dfs와 bfs는 비슷하다고 생각합니다.
스택을 사용하느냐 큐를 사용하느냐의 차이일 뿐인데 해결 방법만 이해하면 어느 하나로 해결해도 상관없다고 생각했다.
이것은 검색이므로 필요한 변수를 먼저 생성해야 합니다.
1. 방문 여부를 결정하기 위해 방문한 어레이
2. 가장자리를 저장하기 위한 2D 배열 가장자리
또한 DFS 과정에서 원이 생성되는지 여부를 판단할 필요가 있다.
판단 방법은 Visited에서 True 처리(방문)한 Node에 한 번 더 접근을 시도하면 Circle이 생성된다는 것입니다.
함수로 만들어 반환값으로 판단하게 했습니다.
+) DFS를 해결하는 과정에서…
처음에는 시간을 줄이기 위해 모서리를 하나만 추가했습니다.
x < y인 경우:
edge(x).append(y)
또 다른:
edge(y).append(x)
이렇게 해서 무조건 작은 값으로 등록을 했고 DFS도 이 방법을 고려해서 검색하게 했습니다.
하지만 이 경우
5 4
1 3
1 4
1 5
2 3
이 입력이 주어졌을 때 문제가 발생했습니다.
위의 Test Case 13으로 올라갔을 때 11번과 12번에서 잘못나와서 2시간동안 고민하다가 왜 잘못된건지 알아냈습니다.
물론 위의 테스트 케이스는 제가 그리지 않았습니다.
노드를 1부터 100까지 그리면서 모서리를 연결할 자신이 없었습니다.
하
메모리와 시간(파이썬)
위는 union & find, 아래는 DFS
| 31256 | 272 |
| 47828 | 392 |
DFS는 훨씬 느리고 많은 메모리를 차지했습니다.
C++ 벡터 사용
C++ 벡터 사용
벡터 C++의 벡터는 동적 배열을 구현하기 위한 표준 템플릿 라이브러리(STL) 컨테이너입니다.
배열과 같은 벡터는 해당 요소를 메모리에 연속적으로 저장하고 동적으로 크기를 조정할 수 있습니다.
휴대용-종이.tistory.com
코드 유니온 찾기
파이썬
import sys
input = sys.stdin.readline
"""
union-find
만약 union을 하는데 이미 있으면 트리에서 제외
-> 2차원 배열로 트리가 아니면 False처리.
모든 간선 계산 후 -> 루트노드의 개수 = 트리의 개수
트리가 아니다 = 사이클이 생겼다.
사이클이 생긴다 = 트리 내부에서 노드간에 간선이 하나 더 연결됐다.
-> find에서 경로압축을 하더라도 상관없다.
이미 union에서 해당 루트노드를 가르키는데 한번 더 가르키라고 지정해버리는 경우가 사이클이 생기는 경우기 때문
"""
def find(x):
if parent(x)(0) !
= x: #루트노드가 아니면
parent(x)(0) = find(parent(x)(0)) #경로압축, 루트노드 찾으러 가기
return parent(x)(0)
return x #루트노드를 찾으면 반환
def union(x, y):
a = find(x)
b = find(y)
if a < b:
parent(b)(0) = a
if parent(a)(1):
parent(a)(1) = parent(b)(1)
elif a > b:
parent(a)(0) = b
if parent(b)(1):
parent(b)(1) = parent(a)(1)
elif a == b:
parent(a)(1) = False #사이클이 생겼으니 False
case = 1
while True:
n, m = map(int, input().split())
cnt = 0
if n == 0:
break
parent = ((j for i in range(2)) for j in range(n + 1))
#union 처리
for i in range(m):
fir, sec = map(int, input().split())
union(fir, sec)
#루트노드 찾기
for i in range(1, n + 1):
if parent(i)(0) == i and parent(i)(1): #루트노드면서 False가 아닌 것
cnt += 1
#출력
if cnt == 0:
print("Case ", case, ": No trees.", sep="")
elif cnt == 1:
print("Case ", case, ": There is one tree.", sep="")
else:
print("Case ", case, ": ", "A forest of ", cnt, " trees.", sep="")
case += 1
C++
#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> parent;
// parent(?)(1)에 사이클이 생기면 1로 저장
int find(int x) {
if (parent(x)(0) == x) {
return x;
}
return parent(x)(0) = find(parent(x)(0));
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x < y) {
parent(y)(0) = x;
if (parent(y)(1) == 1) {
parent(x)(1) = 1;
}
} else if (x > y) {
parent(x)(0) = y;
if (parent(x)(1) == 1) {
parent(y)(1) = 1;
}
} else { // x==y
parent(x)(1) = 1;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int c = 1;
while (true) {
int n, m, cnt = 0;
cin >> n >> m;
if (n == 0)
break;
parent.assign(n + 1, vector<int>(2, 0));
for (int i = 1; i < n + 1; i++) {
parent(i)(0) = i;
}
// merge
for (int i = 0; i < m; i++) {
int start, end;
cin >> start >> end;
merge(start, end);
}
//루트노드로 사이클 확인
for (int i = 1; i < n + 1; i++) {
if (parent(i)(0) == i && parent(i)(1) == 0) {
cnt++;
}
}
//출력
cout << "Case " << c << ": ";
if (cnt == 0) {
cout << "No trees.\n";
} else if (cnt == 1) {
cout << "There is one tree.\n";
} else {
cout << "A forest of " << cnt << " trees.\n";
}
c++;
}
}
코드 DFS
파이썬
import sys
input = sys.stdin.readline
"""
DFS
# 간선을 저장하는 2차원배열 생성
추가로 배열하나에 들렀는지 체크하는 배열 생성(visited)
탐색을 통해서 visited에 이미 들려서 true라면 트리가 아닌걸로
visited에 true라면 트리인지 체크할필요 없음.
"""
#DFS로 circle이 생겼는지 판단후 리턴
def DFS(start):
circle = False
stack = list()
stack.append((start, 0))
while stack:
node, parent = stack.pop()
if not visited(node):
visited(node) = True
for i in edge(node):
if i!
=0 and i!
=parent:
stack.append((i, node))
else:
circle = True
return circle
case = 1
while True:
n, m = map(int, input().split())
if n == 0: break
edge = ((0 for i in range(n + 1)) for j in range(n + 1))
visited = (False for i in range(n + 1))
cnt = 0
#입력
for i in range(m):
x, y = map(int, input().split())
# if x < y:
edge(x).append(y)
# e lse:
edge(y).append(x) #간선 추가
for i in range(1, n + 1):
if visited(i):
continue
if not DFS(i):
cnt += 1
#출력
if cnt == 0:
print("Case ", case, ": No trees.", sep="")
elif cnt == 1:
print("Case ", case, ": There is one tree.", sep="")
else:
print("Case ", case, ": ", "A forest of ", cnt, " trees.", sep="")
case += 1
C++
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> edge;
vector<int> visited;
bool DFS(int start) {
vector<pair<int, int>> stack;
stack.push_back(make_pair(start, 0));
while (!
stack.empty()) {
int node, parent;
node = stack.back().first;
parent = stack.back().second;
stack.pop_back();
if (!
visited(node)) {
visited(node) = true;
for (int i = 0; i < edge(node).size(); i++) {
if (edge(node)(i) !
= parent) {
stack.push_back(make_pair(edge(node)(i), node));
}
}
} else
return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int testCase = 1;
while (true) {
//변수 생성
int n, m, cnt = 0;
cin >> n >> m;
if (n == 0)
break;
edge.assign(n + 1, vector<int>(0));
visited.assign(n + 1, false);
//간선 등록
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
edge(x).push_back(y);
edge(y).push_back(x);
}
// DFS로 트리 개수 파악
for (int i = 1; i < n + 1; i++) {
if (visited(i)) {
continue;
}
if (!
DFS(i)) {
cnt++;
}
}
switch (cnt) {
case 0:
cout << "Case " << testCase << ": No trees.\n";
break;
case 1:
cout << "Case " << testCase << ": There is one tree.\n";
break;
default:
cout << "Case " << testCase << ": A forest of " << cnt << " trees.\n";
}
testCase++;
}
}아직 C++에 익숙하지 않아서 많이 찾아봤습니다.
DFS에서 벡터와 쌍을 억지로 쓰려고 해서 더 복잡해진 것 같은데…