친구인가

친구인가

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 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"를 출력한다.

입력

97 12 23 34 15 67 78 89 38

출력

NO

틀린 구현 코드 - Time Limit Exceeded & 일부 오답

public class 친구인가 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        ArrayList<Friend> info = new ArrayList<>();
        for(int i=0;i<m;i++){
            info.add(new Friend(in.nextInt(),in.nextInt()));
        }

        //친구인지 확인하는 숫자쌍
        Friend find = new Friend(in.nextInt(),in.nextInt());

        int[] root = new int[n+1]; //i번 원소가 속하는 집합의 번호 담는 배열
        for(int i=1;i<=n;i++){
           root[i] = i;
        }

        //친구관계 파악
        for(Friend f : info){
            root[f.f2] = f.f1;
        }

        //i와 root[i]의 값이 같을때까지 타고감.
        int p = root[find.f2];
        boolean flag = true;
        while(p!=find.f1){
            if(root[p] == p) {
                flag = false;
                break;
            }
            p = root[p];
        }

        if(flag){
            System.out.println("YES");
        }
        else{
            System.out.println("NO");
        }

    }

    static class Friend{
        int f1;
        int f2;
        public Friend(int f1, int f2){
            this.f1 = f1;
            this.f2 = f2;
        }
    }
}

• 원래 생각한 알고리즘

  root배열 선언
  root배열을 각 index로 초기화
  (f1,f2)의 관계를 가질 시 root[f2] = f1
  최종적으로 찾는 find의 f1,f2가 주어졌을 때 root[f2]부터 시작해서 찾는 값 f1이 나올때까지 타고 들어감.
  f1이 나오면 flag true.
  최상위 노드까지 도달할때까지 찾는 값이 없으면 flag false.

모범답안 참고 후 구현 코드

public class 친구인가 {
    static int[] unf;
    static int find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=find(unf[v]);
    } //unf[v] = 함으로써 경로 압축

    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 in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.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 = in.nextInt();
            int b = in.nextInt();
            union(a,b);
        }

        int a = in.nextInt();
        int b = in.nextInt();
        int fa = find(a);
        int fb = find(b);
        if(fa==fb) System.out.println("YES");
        else System.out.println("NO");
    }
}

• 알고리즘

  unf배열 n+1 사이즈로 선언
  각 배열원소를 해당 index로 초기화
  주어진 관계에 따라 union수행.
  최종적으로 친구인지 확인하는 a,b에 대해서 find(a), find(b) 값이 같으면 YES, 다르면 NO

• 경로압축

 static int find(int v){
        if(v==unf[v]) return v;
        else return **unf[v]=find(unf[v]);**
    } //unf[v] = 함으로써 경로 압축

unf[v]=find(unf[v]); -> 경로 압축

Disjoint-Set : Union&Find 관련 자료를 찾아보니 배열과 트리로 풀 수 있고 트리구조로 구현하는게 좀 더 효율적인 것 같다.

참고

Union&Find
배열과 트리로 구현 차이