[백준]알고리즘_유니온파인드(백준1717, 백준1976)
유니온 파인드 알고리즘(==서로소 집합, 상호 베타적 집합)
두 노드가 같은 그래프에 속하는지 판별하는 알고리즘으로 노드를 합치는 union / 노드를 찾는 find연산으로 구성
트리 구조로 이루어진 자료구조 / 시간복잡도는 = 0(1)
|
인덱스
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
부모노드
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
임의로 UNION(보통 INDEX가 작은 쪽이 부모노드가 됨). 1-2번, 4-6-7-번 연걀해범
|
인덱스
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
부모노드
|
1
|
1
|
3
|
4
|
4
|
6
|
4
|
<x-y 연결해주는 함수>
Union(x,y)
x= find(x); y=find(y);
if x!= y
if x<y ->parent[y] = x
else -> parent[x] = y
1)루트, y 루트 연결해줌 2)x와 y과 같지 않으면 3)y가 더 크다면(인덱스가 더 크다면) y의 부모함수는 x이고 그 반대면 반대로 지정
<x의 루트노드 찾는 함수>
Find(x)
If x == parent >> return
Return parent[x] = find(parent[x]) // 재귀 사용
1)x가 부모함수라면 그냥 return 아니면 x의 부모함수를 찾는것
>> 즉 find메서드를 통해 부모노드를 찾고 부모가 같지 않다면 union함수를 이용하여 붙여주는 방식이다
백준 1717번
문제 : 초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오.
해결방법
n,m만큼 입력 받고 배열 n을 초기화 시켜줌 > 첫번째값이 0인 경우 union > 부모 같은지 확인하고 출력값 내보내기
위의 쓰여진 함수를 자바에서 우선 구현시킴
Main
main절 변수입력은 필요할때마다 입력해줌. main절에서 n/m입력받고 부모노드만들어줄 배열 하나 선언 후 초기화
출력값 비교하는 부분. 입력값 넣어줌(한줄 띄어넣고 넣주니까 st=newStringTkenizer 빼먹지 않기 처음에 이래서 틀림...;;)
swith~case문을 이용하여 출력문 제시함
0일때는 y-z union 함수 이용해서 합치고, 다른 경우 루트노드를 찾아주거나 루트노드 연결되지 않으면 no출력
백준 1976번
문제: 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
해결방법
양방향으로 연결되어있기 떄문에 한번 연관된 도시는 같은 부모를 가지고 있구나 생각...!
주어진 행렬이 1이라면 합친 노드가 없으므로 union함수 이용해서 한번 합쳐주기
(*중복하는 것 방지!! (2,3)과 (3,2)를 입력받으면 안됨)
맨 처음 도시를 find해서 루트 노드 찾기
i번째 수행한 루트 노드와 i~n도시에서 수행한 노드 비교해서 같은 경우 yes, 다른 경우 no
위의 find, union 함수는 그대로 가져다 씀
똑같이 n과 m을 입력받고 부모배열까지 초기화해줌
1~n까지 for문을 돌려서(실수하지 않기) 연결해줌. 주어진 행렬이 1이라면 합친 노드가 없으므로 union함수 이용해서 한번 합쳐주기!!!
이 부분은 출력하는 부분
yes를 기본으로 잡고 전꺼와 비교했을 때 서로 연결되지 않으면 no라고 해줌
여기서 또 for문 범위 잡는 거 틀림ㅎㅎ.... 1부터 시작하고 배열은 index에서 -1해줘야하기 떄문이다...
