1976번: 여행 가자 (acmicpc.net) 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 풀이: 문제에 나와 있는 거 문장을 보면 `같은 도시를 여러 번 방문하는 것도 가능하다.`라고 나와 있다. 여행 계획의 시작 지점을 시작으로 경로를 가기 위한 edge가 이어져 있다면 어떤 방법으로든 여행 계획을 한 번씩 들려서 목적지까지 도달할 수 있다. 밑에는 백준 문제에 예시를 그림으로 표현하고 배열의 인덱스에 맞는 value 값을 표현한 것이다. ..

20040번: 사이클 게임 (acmicpc.net) 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 사이클 찾기: 여기서 빨간색 줄을 마지막으로 연결한다고 가정했을때, 왼쪽은 3번 키값의 value는3, 5번키값의 value는 3으로 같고, 오른쪽은 5번 키값의 value는3, 1번키값의 value는 1로 다르다. 이렇게 사이클은 새로운 edge를 추가할때 출발점의 부모와 도착점의 부모가 같으면 사이클이 발생했다고 판단한다. 3. 구현:

Union-Find(유니온 파인드)그래프 알고리즘 중 하나로 서로소(disjoint sets) 집합 자료구조이다. 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.1. union(합집합)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.       - A와 B의 루트 노트 A', B'를 각각 찾는다.       - A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.17. Union-Find(..