[JAVA] 알고리즘 문제풀이 - Greedy 기출문제 (친구인가?)
Greedy기출문제 풀이
친구인가? (Disjoint-Set : Union&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개의 줄에 걸쳐 숫자쌍이 주어진다. 마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.
-
출력 : 첫 번째 줄에 “YES”또는 “NO”를 출력한다.
-
풀이 답안 (개선 전)
import java.util.*;
public class Main {
static List<List<Integer>> list = new ArrayList<>();
static int[] dis;
public String solution(int n, int m) {
Queue<Integer> q = new LinkedList<>();
q.offer(n);
while(!q.isEmpty()) {
int tmp = q.poll();
dis[tmp] = 1;
for (Integer integer : list.get(tmp)) {
if(dis[integer]!=1){
q.offer(integer);
}
}
}
return (dis[m]==0) ? "NO" : "YES";
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
int stu = scan.nextInt();
dis = new int[stu+1];
for(int i=0; i<=stu; i++){
list.add(new ArrayList<Integer>());
}
int e = scan.nextInt();
for(int i=0; i<e; i++){
int a = scan.nextInt();
int b = scan.nextInt();
list.get(a).add(b);
list.get(b).add(a);
}
int n = scan.nextInt();
int m = scan.nextInt();
System.out.println(main.solution(n, m));
}
}
- 정리
- 초기에는 일반적인 리스트 형식, 단 양방향인 리스트 형식이라 생각했기에 보통 풀었던 이중 리스트 풀이에, 기준 정점을 양쪽에 담아주는 방식으로 풀이했다
- 그러나 이렇게 풀이하는게 아니라 집합 형식으로 풀이하는게 훨씬 효율적임을 알게되어 아래 방식으로 재 풀이함
- 초기에는 일반적인 리스트 형식, 단 양방향인 리스트 형식이라 생각했기에 보통 풀었던 이중 리스트 풀이에, 기준 정점을 양쪽에 담아주는 방식으로 풀이했다
- 풀이 답안 (개선)
import java.util.*;
public class Main {
static int[] f;
public static int Merge(int v) {
if(v==f[v]) return f[v];
else return f[v] = Merge(f[v]);
}
public static void Union(int a, int b){
int f_a = Merge(a);
int f_b = Merge(b);
if(f_a!=f_b) f[f_a] = f_b;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
f = new int[n+1];
for(int i=1; i<=n; i++){
f[i] = i;
}
int m = scan.nextInt();
for(int i=0; i<m; i++){
int a = scan.nextInt();
int b = scan.nextInt();
Union(a, b);
}
int ra = scan.nextInt();
int rb = scan.nextInt();
if(Merge(ra)==Merge(rb)) System.out.println("YES");
else System.out.println("NO");
}
}
- 정리
- 입력받는 부분부터 변동 사항이 생기기에 모두 재설명함
- 우선 각 정점의 수를 입력받은 후 정점+1 (0인덱스는 사용하지 않기때문)사이즈의 배열을 만들고 각 배열에 인덱스와 동일한 값을 채워줌
- 몇개의 선이 있는지 받은후 그만큼 반복을 통해 입력을 받는데
- 입력을 받음과 동시에 Union이라는 함수를 만들어 매개변수로 입력받은 두 정점을 넘겨줌
- Union에서는 입력받은 두 정점을 Merge 함수로 넘기고 두개의 값이 같은지 확인함
- Merge에서는 현재 넘어온 매개변수의 수가 처음 만든 배열(이하 f) 인덱스에 담긴 데이터 값과 같은지 비교 함
- 예를들어 1이 넘어왔을때 1과 같으면 그대로 1을 반환. 만약 2가 담겨져있다면 Merge(f[1])인 Merge(2)를 찾아오고 f[2]가 2라면 2를 반환 만약 5가 담겨져있다면 Merge(f[2])인 Merge(5)를 재탐색 하는 방식.
- 이렇게 두 수의 값을 모두 찾았다면 Union에서는 다시 두 수가 같은지(=두 수가 같은 집합인지) 확인해보고
- 두 수가 이미 같은 집합이라면 별도로 해야하는 후작업이 없으나 다른 집합이라면 이제 두 수는 친구이기 때문에 같은 집합으로 묶어줘야함
- 따라서 f[f_a]의 값을 f_b의 값으로 바꾸어 줌. 이렇게 되면 f[a]에서 f[f_a]까지 같은 집합. f[b]부터 f[f_b]까지가 같은 집합으로 되어있는 상황에서 f[f_a]와 f[f_b] 역시 같은 집합으로 묶여 모두 연계되는것
- 이런식으로 입력받은 데이터를 묶은 뒤 다시 메인에서 최종으로 친구인지 확인해야 하는 데이터를 받게되면
- 다시 Merge 함수를 통해서 Merge(ra)의 값과 Merge(rb)의 값이 같은지만 확인해보면 됨
- 입력받는 부분부터 변동 사항이 생기기에 모두 재설명함