Cos Pro 1급 - 샘플 문제 5차 7번 - 그래프에서 사이클 찾기(Find-Union)

문제 지문 #7

그래프의 노드 수와 노드 연결 순서가 주어질 때, 몇 번째 연결에 사이클이 생기는지 알고 싶습니다. 예를 들어, 노드가 3개이고 노드를 [[1, 2], [1, 3], [2, 3]] 순으로 연결한다면 아래 그림과 같습니다.

• 1번째 연결
•  
• 
• 2번째 연결
• 
• 3번째 연결
• 

따라서 3번째 연결에서 사이클이 생깁니다.

그래프의 노드 수 n, 노드 연결 순서 connections가 매개변수로 주어질 때, 몇 번째 연결에 사이클이 생기는지 return 하도록 solution 메서드를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

---

#####매개변수 설명
그래프의 노드 수 n, 노드 연결 순서 connections가 solution 메서드의 매개변수로 주어집니다.

• 그래프의 노드 수 n은 3 이상 10 이하입니다.
• connections은 길이가 3 이상 50 이하인 배열입니다.
• connections 배열의 각 행은 [a, b]는 a번 노드와 b번 노드를 연결한다는 의미입니다.
• 항상 사이클이 생기는 경우만 주어집니다.

---

#####return 값 설명
몇 번째 연결에서 사이클이 생기는지 return 합니다.

---

#####예제

n	connections	return
3	[[1, 2], [1, 3], [2, 3]]	3

#####예제 설명
문제에 나온 예와 같습니다.

728x90

 

혼자 풀이

빈칸 채우기 문제입니다. 

그래프에서 Union-Find 알고리즘을 사용하는 문제입니다. Union-Find 알고리즘은 상호 배타적 집합을 표현할 때 사용합니다. 여기서 상호 배타적 집합이란, 전체 집합을 여러 개로 쪼갰을 때, 각 소집합 간에 공통 원소가 없다는 것을 뜻합니다.

가령 1부터 10까지의 수가 있고, 이 두 집합을 짝수와 홀수로 나누었을 때, 두 집합 모두에 속하는 원소는 없습니다. 이런 경우를 상호 배타적이라고 합니다. 그래프에서도 1부터 10까지의 노드가 있고, 몇 개의 노드로 구성된 작은 그래프로 나누었을 때, 한 개의 노드가 두 개의 집단에 속하지 않으므로 상호 배타적이라고 할 수 있습니다.

이런 상호 배타적 집합을 표현하기 위해 아래와 같은 세가지 연산이 필요합니다.

- 초기화: n개의 원소가 각각의 집합에 포함되어 있도록 초기화합니다.
- 합치기(Union) 연산: 두 원소 a, b가 주어질 때, 이들이 속한 두 집합을 하나로 합칩니다.
- 찾기(Find) 연산: 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환합니다.

합치고 찾는 두 가지 연산을 지원한다고 해서 Union-Find 알고리즘이라고 부릅니다.
이 문제에서는  Union-Find 알고리즘으로 아래와 같이 사이클을 판별합니다.

1. Find 함수로 부모 노드를 찾는다.
2. 연결하려는 A노드와 B노드의 부모 노드를 비교한다.
    1) 부모 노드가 같으면 사이클이 만들어짐(아직 사이클이 아니지만 연결하면 사이클이 됨)
    2) 부모 노드가 다르면 두 노드 중 큰 번호를 부모 노드로 설정한다(Union)
3. 1,2를 사이클이 만들어질 때까지 반복한다. 

이 아이디어를 가지고 문제를 풀어봅니다.

문제에서 주어진 각 노드의 연결 순서는 다음과 같습니다.

{1, 2}, {1, 3}, {2, 3}

[초기화] 우선 노드의 개수는 3개이며, Find-Union 첫 번째 단계인 초기화를 합니다. 이에 따라 1, 2, 3 노드의 부모 노드는 1, 2, 3으로 초기화됩니다.

[1,2 연결] 1, 2 노드를 연결합니다. 각 노드의 부모 노드를 찾아서(Find) 두 개의 부모 노드가 다르므로 두 노드가 속한 그래프를 연결합니다(Union). 이때, 1의 부모 노드를 더 큰 노드인 2로 변경합니다.

[1,3 연결] 1, 3 노드를 연결합니다. 1의 부모 노드는 2이고, 3의 부모 노드는 3이므로 서로 다릅니다. 따라서 1과 3이 속한 그래프를 연결합니다. 이때, 2의 부모 노드는 3이 됩니다..
(※ 주의: 1의 부모 노드를 바로 3으로 변경하는 것이 아니라 1의 부모 노드인 2의 부모 노드를 3으로 변경합니다.)

[2,3 연결] 2, 3 노드를 연결합니다. 2의 부모 노드는 3이고, 3의 부모 노드도 3으로 동일하므로 사이클이 만들어집니다.

아래 코드에 주석도 달아놓았습니다.

class Main {
    public int find(int[] parent, int u) {
        if(u == parent[u])  //노드와 노드의 부모노드가 같으면 해당노드를 반환
            return u;
        // parent[u] = @@@;
        parent[u] = find(parent,parent[u]);//노드와 노드의 대표노드가 다르면 find를 재귀호출하여 대표노드의 대표노드를 찾음
        return parent[u];
    }

    public boolean merge(int[] parent, int u, int v) {
        u = find(parent, u); //u의 부모노드를 찾음
        v = find(parent, v);

        if(u == v) //두 노드의 부모가 같으면 사이클이 생긴 것
            return true;
        // @@@;
        parent[u]=v; //두 노드의 부모가 다르면 u의 부모노드를 v로 변경하고 false를 리턴(여기서 병합됨)
        return false;
    }
    //그래프 이론을 알아야 풀 수 있는 문제입니다.
    //그래프 이론에서 싸이클을 판별하기 위해서는 합집합-찾기(Union-Find) 알고리즘을 알아야 합니다.
    //Union은 서로다른 대표노드(부모노드)를 가지는 그래프를 합쳐서 같은 대표노드(부모노드)를 가지도록 만드는 함수(여기서는 merge)
    //Find는 그래프의 대표노드를 찾는 함수(find)
    public int solution(int n, int[][] connections) {
        int answer = 0;

        int[] parent = new int[n+1]; //부모노드를 자기자신으로 초기화 한다.
        for(int i = 1; i <= n; i++)
			// @@@;
            parent[i]=i;

        for(int i = 0; i < connections.length; i++) //노드를 순차적으로 연결
			//merge하여 싸이클이 발생하면 break 하여 answer를 반환
            if(merge(parent, connections[i][0], connections[i][1])) { 
                answer = i + 1;
                break;
            }

        return answer;
    }

    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        Main sol = new Main();
        int n = 3;
        int[][] connections = {{1, 2}, {1, 3}, {2, 3}};
        int ret = sol.solution(n, connections);

		// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret + " 입니다.");
    }
}

 

정답

혼자 풀이와 정답이 동일합니다.

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)

 

참고 자료

 

- 책: 알고리즘 문제 해결 전략(인사이트, 구종만 지음)