728x90
문제
https://www.acmicpc.net/problem/1717
문제 풀이
이 문제는 다른 거 할 거 없이 Union-Find 알고리즘만 적용하면 되는 문제입니다.
2022.07.24 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] Union-Find 알고리즘
각 줄에서 맨 처음에 오는 숫자는 연산을 의미합니다.
0은 union
1은 find
따라서 이 연산에 맞게 각 노드의 연결관계를 set 또는 get 하시면 됩니다!
Union-Find 알고리즘은 위의 글에서 세세하게 설명하니 참고하셔서 풀면 될 것 같네요 ㅎ
구현
코드
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# 노드의 루트 노드를 찾는 함수
def find(v):
if v != rootList[v]:
rootList[v] = find(rootList[v])
return rootList[v]
# 루트 노드에 따라 합!
def union(v1, v2):
v1 = find(v1)
v2 = find(v2)
if v1 < v2:
rootList[v2] = v1
else:
rootList[v1] = v2
# 두 노드가 같은 집합에 있는지 확인하는 함수
def is_same_sec(v1, v2):
v1_root = find(v1)
v2_root = find(v2)
if v1_root == v2_root:
return True
else:
return False
if __name__ == "__main__":
n, m = map(int, input().split())
rootList = list(range(n+1))
for _ in range(m):
op, v1, v2 = map(int, input().split())
if op == 0:
union(v1, v2)
elif op == 1:
if is_same_sec(v1, v2):
print('YES')
else:
print('NO')
결과
728x90
반응형
'PS > 백준' 카테고리의 다른 글
[백준(BOJ)] #1197- 최소 스패닝 트리 (파이썬, Python3) (3) | 2022.08.02 |
---|---|
[백준(BOJ)] #1463- 1로 만들기 (파이썬, Python3) (0) | 2022.07.26 |
[백준(BOJ)] #11000- 강의실 배정 (파이썬, Python3) (2) | 2022.07.23 |
[백준(BOJ)] #2263- 트리의 순회 (파이썬, Python3) (0) | 2022.07.20 |
[백준(BOJ)] #1285- 동전 뒤집기 (파이썬, PyPy3) (0) | 2022.07.18 |