[문제풀이] 09-06. 친구인가

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0906. 친구인가(Union & Find)

---

🗒️ 문제

---

🎈 나의 풀이

	private static List<List<Integer>> relation = new ArrayList<>();
    private static int[] ch;
    private static int n, m;

    private static String solution(int a, int b) {
        Queue<Integer> Q = new LinkedList();
        Q.add(a);

        while(!Q.isEmpty()) {
            int man = Q.poll();
            ch[man] = 1;

            for(int x : relation.get(man)) {
                if(x == b) return "YES";
                if(ch[x] == 0) Q.add(x);
            }
        }

        return "NO";
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        ch = new int[n+1];

        for(int i=0; i<=n; i++) relation.add(new ArrayList<>());

        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            relation.get(a).add(b);
            relation.get(b).add(a);
        }

        System.out.println(solution(sc.nextInt(), sc.nextInt()));
    }

---

🖍️ 강의 풀이

  static int[] unf;
	public static int Find(int v){
		if(v==unf[v]) return v;
		else return unf[v]=Find(unf[v]);
	}
	public static void Union(int a, int b){
		int fa=Find(a);
		int fb=Find(b);
		if(fa!=fb) unf[fa]=fb;
	}
	public static void main(String[] args){
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		unf=new int[n+1];
		for(int i=1; i<=n; i++) unf[i]=i;
		for(int i=1; i<=m; i++){
			int a=kb.nextInt();
			int b=kb.nextInt();
			Union(a, b);
		}
		int a=kb.nextInt();
		int b=kb.nextInt();
		int fa=Find(a);
		int fb=Find(b);
		if(fa==fb) System.out.println("YES");
		else System.out.println("NO");		
	}

---

💬 짚어가기

해당 문제는 Union & Find를 이용하여 해결할 수 있으나, 나의 풀이에서는 다른 방식으로
구현하였다. 우선 Integer를 요소로 갖는 List를 생성하였고, 이 리스트들을 보관할 수
있는 relaion : List<List<Integer>>를 생성하였다.

각 학생의 번호를 relaion 리스트의 인덱스와 매치되게 하고, 입력에 맞추어 relation
리스트를 채운 뒤, Queue를 이용하여 한 친구의 모든 친구 관계를 순회하며 두 친구 사이에
관계가 있는지 확인하s는 로직이다.

강의에서는 Union & Find를 이용하여 친구 관계를 하나의 트리로 만들도록하였다.
인덱스가 학생의 번호를 의미하는 배열 unf를 생성하고, 해당 요소가 가진 값은 친구의
인덱스를 바라보도록 하여 친구 관계를 나타낸다.

Find 메소드
Find 메소드는 해당 학생이 포함된 친구 관계(무리)를 확인할 수 있다.

public static int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

아직 친구 관계가 없는 경우 자기 자신을 반환하고, 친구가 존재하는 경우의 재귀 호출을 통해
친구 무리 중 가장 끝(위)에 위치한 친구를 반환한다.

리턴문의 unf[v]=Find(unf[v]) 코드는 친구 관계를 나타내는 트리를 압축하여 더욱 빨리
탐색할 수 있도록 해준다.

Union 메소드
Union 메소드는 두 친구가 같은 무리가 아닌 경우 한 무리의 가장 끝(위)에 위치한 친구가 다른
무리의 가장 끝(위)에 위치한 친구를 바라보도록 하여 두 무리를 하나로 합친다.

public static void Union(int a, int b){
	int fa=Find(a);
	int fb=Find(b);
	if(fa!=fb) unf[fa]=fb;
}

모든 입력(친구 관계)에 대한 Union을 수행한 후, Find를 통해 두 친구가 같은 무리인지 확인한다.