섹션 9. Greedy Algorithm 6. 친구인가(Uion&Find)

문제

• 오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.
• 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.
• 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.
• 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.
• 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.
• 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

입력

• 첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이 주어지고,
• 다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.
• 마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

출력

• 첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

입출력 예제

---

풀이방식

이번 문제는 그리디 알고리즘에 대한 문제이다.

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

---

설계과정

1. v 번째 학생의 집합번호를 리턴해주는 Find 메소드를 작성한다.

2. Find 메소드를 통해 얻은 정보로 집합 번호와 학생 번호를 비교하는 Union 메소드를 작성한다.

3. Find, Union 메소드를 계속 수행해서 결과를 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 서로소 집합을 가진  unf[ ] 을 선언한다.
• 앞의 학생의 집합번호를 담을 fa 을 선언한다.
• 뒤의 학생의 집합번호를 담을 fb 을 선언한다.
• 학생 수를 의미하는 변수 N 을 선언한다.
• 순서쌍의 개수를 의미하는 변수 M 을 선언한다.
• 즉, 7개의 순서쌍을 통해 unf 배열을 완성하고, 마지막에 입력된 값으로 두 학생이 친구 사이인지 확인한다.

2. v 번째 학생의 집합 번호를 리턴하는 Find 메소드를 작성한다.

 

3. v번째 학생과 해당 학생의 집합 번호가 동일하면 v 를 그대로 리턴한다.

 

4. 다르다면 Find(unf[v]) 를 unf에 넣는다.

• 해당 일자에 해당하는 강의만 확인하고, 그 중 큰 값을 비교하기 위해서이다.

5. 같은 집합 번호인지 확인하는 Union 메소드를 작성한다.

 

6. fa와 fb가 다르다면 unf[fa]에 fb 값을 넣는다.

 

7. Find와 Union 메소드를 수행하면 아래와 같다.

• (1, 2)를 예시로 들어보자.
• 처음 unf 배열은 다음과 같다.

• Find 메소드를 수행한다.
• 1을 보면 v와 unf[v]가 1로 값이 같기에 1을 리턴하고, 2도 마찬가지이다.
• 다음으로 Union 메소드를 수행한다.
• fa는 1, fb는 2이기에 unf[fa] 를 fb 즉, 인덱스 1번과 2번의 값이 전부 2로 만든다.

8. 위 과정을 반복해서 unf 배열을 완성한 후, 결과를 위한 두 학생의 집합번호를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.