본문 바로가기
반응형

Problem Solving/Union-Find & Minimum Spanning Tree4

[유니온-파인드] 백준 3108번: 로고 / 골드 3 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) points = [] original = False for i in range(n): a, b, c, d = map(int, input().split()) points.append([a, b, c, d]) if a == 0 or c == 0: if b y2 or y4 < y1: return False if x1 .. 2021. 8. 21.
[유니온-파인드] 백준 20040번: 사이클 게임 / 골드 4 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net import sys input = sys.stdin.readline n, m = map(int, input().split()) parents = [i for i in range(n)] def find(parent, x): if parent[x] == x: return x else: return find(parent, parent[x]) def union(parent, a, b): a = fi.. 2021. 8. 19.
[최소신장트리] 백준 4386번: 별자리 만들기 / 골드 4 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net import sys import math input = sys.stdin.readline n = int(input()) starts = [] for i in range(n): a, b = map(float, input().split()) starts.append([a, b]) parents = [i for i in range(n)] graph = [] for i in range(n-1): for j.. 2021. 8. 19.
[ 최소 신장 트리 ] 백준 1922번: 네트워크 연결 / 골드 4 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, a, b): a = find(parent, a) b = find(parent, b) if a < b: parent[b] = a else: parent[a] = b import sys n = int(input()) m = int(input()) parent = [0]*(n+1) edges = .. 2021. 7. 29.
반응형

티스토리툴바