[알고리즘_코딩 테스트_JAVA] 그래프-유니온 파인드 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 050 집합 표현하기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

▪️ 유니온 파인드

union 연산: 각 노드가 속한 집합을 1개로 합치는 연산

find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

▪️구현 핵심

• 각 노드를 자신의 인덱스값으로 초기화
• union은 항상 대표노드끼리 연결해 준다.
• find 연산은 그래프를 정돈하고 시간 복잡도를 줄인다.

▪️find 연산

• index 값과 value 값이 동일한지 확인
• 동일하지 않으면 value 값이 가리키는 index 위치로 이동
• 이동 위치의 index값과 value값이 같을 때까지(대표 노드 찾을 때까지) 반복
• 대표 노드에 도달하면 재귀를 빠져나오며 거치는 모든 노드값을 대표 노드값으로 변경

▪️실수 주의 😲

경로 압축은 늘 해주기! (재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견한 대표노드로 변경)union 연산에서 선택된 노드끼리 연결 X 대표 노드끼리 연결하기!

슈도코드 작성하기

N(원소 개수) M(질의 개수)
parent(대표 노드 저장 리스트)

# find 연산
find(a):
    a가 대표 노드면 리턴
    아니면 a의 대표 노드값을 find(parent[a]) 값으로 저장->재귀함수 형태

# union 연산
union(a, b):
    a와 b의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결

#checkSame -> 두 원소가 같은 집합인지 확인
checkSame(a, b):
    a, b의 대표 노드 찾기
    두 대표 노드가 같으면 true
    아니면 false return

for N만큼 반복:
    대표 노드를 자기 자신으로 초기화

for M만큼 반복:
    if 질의가 0:
        집합 합치기 -> union 연산
    else:
        같은 집합 원소인지 확인하고 결괏값 출력

JAVA

import java.util.*;

public class Main {
    public static int[] parent;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        parent = new int[N + 1];
        for(int i = 0; i <= N; i++){ // 대표 노드를 자기 자신으로 초기화
            parent[i] = i;
        }
        for(int i = 0; i< M; i++){
            int question = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(question == 0){ // 0 ; 집합 합치기
                union(a, b);
            }else{
                if(checkSame(a, b)) { // 같은 집합인지 확인
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a!=b) {
            parent[b] = a;
        }
    }
    public static int find(int a) {
        if (a == parent[a]){
            return a;
        } else{
          return parent[a] = find(parent[a]); // 재귀 함수의 형태로 구현 -> 경로 압축  
        }
    }
    public static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        if (a==b){return true;}
        return false;
    }
}

PYTHON

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
parent = [0] * (N + 1)

def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a] = find(parent[a]) # 경로압축
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a

def checkSame(a, b): # 두 원소가 같은 집합에 속해 있는지 확인하는 함수
    a = find(a)
    b = find(b)
    if a == b:
        return True
    return False

# 자기 자신으로 초기화
for i in range(0, N + 1):
    parent[i] = i

for i in range(M):
    question, a, b = map(int, input().split())
    if question == 0:
        union(a, b)
    else:
        if checkSame(a,b):
            print("YES")
        else:
            print("NO")

 

✔ 문제 051 여행 계획 짜기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

▪️ 유니온 파인드

▪️구현 핵심

• 인접 행렬로 주어졌기때문에, 인접 행렬을 탐색하며 도시가 연결돼 있을때 union 연결을 수행한다.
• 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인 후 결괏값을 출력한다.

JAVA

import java.util.*;

public class Main {
    public static int[] parent;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] adj = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++){ // 도시 연결 데이터 저장
            for(int j = 1; j <= N; j++){
                adj[i][j] = sc.nextInt();
            }
        }
        int[] path = new int[M + 1]; // 도시 정보 저장
        for(int i = 1; i <= M; i++){
            path[i] = sc.nextInt();
        }
        parent = new int[N + 1];
        for(int i = 1; i <= N; i++){ // 대표 노드를 자기 자신으로 초기화
            parent[i] = i;
        }
        for(int i = 1; i <=N; i++){ // 도시가 연결되어있으면 union
            for(int j = 1; j <=N; j++){
                if(adj[i][j] == 1) union(i, j);
            }
        }
        // 여행 계획 도시들이 1개의 대표 도시로 연결돼 있는지 확인
        int index = find(path[1]);
        for(int i = 2; i < path.length; i++){
            if (index != find(path[i])){
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
    public static void union(int a,int b){
        a = find(a);
        b = find(b);
        if(a != b){
            parent[b] = a;
        }
    }
    public static int find(int a){ // find 연산
        if(a == parent[a]){
            return a;
        } else{
            return parent[a] = find(parent[a]); // 재귀 함수 형태로 구현 -> 경로 압축 부분
        }
    }
}

PYTHON

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])  # 재귀 / 경로압축
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a

N = int(input())
M = int(input())
adj = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    adj[i] = list(map(int, input().split()))
    adj[i].insert(0, 0)

path = list(map(int, input().split()))  # 여행 경로 정보 저장
path.insert(0,0)

# parent 초기화
parent = [0] * (N + 1)
for i in range(1, N + 1):
    parent[i] = i

for i in range(1, N + 1):  # 인접행렬에서 도시가 연결되어 있으면 union
    for j in range(1, N + 1):
        if adj[i][j] == 1:
            union(i, j)

presentNode = find(path[1])
isConnected = True
for i in range(1, len(path)):
    if presentNode != find(path[i]):
        isConnected = False
        break

if isConnected:
    print("YES")
else:
    print("NO")

✔ 문제 052 거짓말

문제 바로가기 💨 

 

⬜ 핵심 아이디어

▪️ 유니온 파인드

진실을 아는 사람들중 한명이라도 각 파티와 이어져 있는지(같은 그룹인지 = 대표 노드가 같은지) 확인한다.

 

풀이 방법

• 먼저 각 파티 행마다 union을 써서 같은 그룹으로 합쳐준다.
• 그리고 다시 각 파티 행마다 각 파티그룹에 진실을 아는사람이 있는지 확인한다.
• 이는 즉, 파티 대표그룹에 진실을 아는 사람이 한명이라도 속해있는지, 다시 말하면 대표 노드가 같은지 확인하는것이다.

이 문제는 입력값을 어떻게 받을지에서 고민했다. 허허... 입력은 아래값이 차례로 주어진다.

사람수, 파티수
진실을 아는 사람수, 번호들
파티인원, 참여번호들
...

파이썬을 기준으로 살펴보자.

여기서 일단 진실을 아는 사람들리스트를 저장할때는 list(map(...)) 형식으로 진실 아는 사람들, 번호들을 쭉 담아주고 del arr[0]을 통해 진실을 아는사람들 번호만 남긴다. 그리고 파티는 party = [[] for _ in range(M)] 을 통해 인접리스트로 구현한다. 그리고 각 파티 정보 줄마다 파티데이터를 list(map(...)) 형식으로 저장후, del party[i][0] 을통해 삭제해줌을 통해 파티 참여 인원 번호들만 남겨준다.

 

자바에서는 sc.nextInt()를 사용해 인원수를 먼저받고, for문을 돌며 진실을 아는 사람들을 저장했다.그리고 ArrayList<Integer> 동적배열을 통해 파티 정보를 저장했다.

JAVA

import java.util.*;

public class Main {
    public static int[] parent;
    public static int[] trueP;
    public static ArrayList<Integer>[] party;
    public static int result;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();
        result = 0;
        trueP = new int[T];
        for(int i = 0; i < T; i++){ // 진실을 아는 사람들 저장
            trueP[i] = sc.nextInt();
        }
        party = new ArrayList[M];
        for (int i = 0; i < M; i++){
            party[i] = new ArrayList<Integer>(); // 파티 데이터 저장
            int party_size = sc.nextInt();
            for (int j = 0; j < party_size; j++){
                party[i].add(sc.nextInt());
            }
        }
        // 대표 노드를 자기 자신으로 초기화
        parent = new int[N + 1];
        for (int i = 0; i <= N; i++){
            parent[i] = i;
        }
        for (int i = 0; i < M; i++){ // 파티 참여 그룹 union
            int first = party[i].get(0);
            for(int j = 1; j < party[i].size(); j++){
                union(first, party[i].get(j));
            }
        }
        // 진실아는 사람들이 각 파티에 한명이라도 있다면(대표노드 같다면) 거짓말 못한다.
        for (int i = 0; i < M; i++){
            boolean isPossible = true;
            int cur = party[i].get(0);
            for (int j = 0; j < trueP.length; j++){
                if(find(cur) == find(trueP[j])) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible) result++; // 모두 다르면 결괏값 1 증가
        }
        System.out.println(result);
    }
    
    //union
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b){
            parent[b] = a;
        }
    }
    //find
    public static int find(int a){
        if (a==parent[a]) return a;
        else
            return parent[a] = find(parent[a]);  //재귀 함수
    }
    public static boolean checkSame(int a, int b){
        a = find(a);
        b = find(b);
        if (a==b){
            return true;
        }
        return false;
    }
}

PYTHON

N, M = map(int, input().split())
trueP = list(map(int, input().split())) # 진실 아는 사람
T = trueP[0] # 진실을 아는 사람 수
del trueP[0]
result = 0
party = [[] for _ in range(M)]
parent = [i for i in range(0, N + 1)]

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
        
def union(a, b):
    a = find(a)
    b = find(b)
    
    if a!=b:
        parent[b] = a
        
def checkSame(a, b): # 대표 노드 같은지 확인
    a = find(a)
    b = find(b)
    if a == b:
        return True
    return False

for i in range(M):
    party[i] = list(map(int,input().split())) # 파티 데이터 저장
    del party[i][0]

# 각 파티에 참여한 사람을 한개의 그룹으로 만들기
for i in range(M):
    first = party[i][0]
    for j in range(1, len(party[i])):
        union(first,party[i][j])

# 각 파티와 진실 아는 사람들중 한명이라도 같은 그룹이면 (대표노드가 같으면) 과장할 수 없다.
for i in range(M):
    isPossible = True
    firstPeople = party[i][0]
    for j in range(len(trueP)):
        if find(firstPeople) == find(trueP[j]):
            isPossible = False
            break
    if isPossible:
        result += 1 # 모드 다르면 결괏값 증가

print(result)