그래프 알고리즘 문제의 기본 스킬1

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 전력망을 둘로 나누기

 

n개의 송전탑이 전선을 통해 하나의 트리형태로 연결되어 있습니다.

 

당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다.

 

이 때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추려고 합니다.

 

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다.

 

전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때,

 

두 전력망이 가지고 있는 송전탑 개수의 차이(절댓값)를 return하도록 solution 함수를 완성해주세요

 

 

2. 제한사항

 

n은 2이상 100이하 자연수

 

wires는 길이가 n-1인 정수형 2차원 배열

 

wires의 각 원소는 [v1,v2] 2개의 자연수로 이루어져 있으며 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것

 

$1 \leq v1 < v2 \leq n$

 

전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않는다

 

 

3. 예시

 

 

4. 예시설명

 

 

 

 

 

5. 나의 풀이

 

핵심방법은 서로 연결된 node끼리 2개의 그룹으로 나누는 것이다

 

def solution(n, wires):
    
    from collections import deque
    
    answer = -1
    
    wires_deque = deque(wires)
    
    list_one = []
    
    list_two = []

 

deque를 사용한 이유는 넣고 빼는데 걸리는 시간을 줄이기 위해서

 

완전탐색법을 사용하고자 한다

 

wires_deque에 들어간 선분 하나 제거해보고

 

두 집단으로 나눈다음에 node 차이 확인해보는 작업을

 

모든 선분 제거해보면서 확인해보는거

 

for remove_ind in range(n-1):
    
    a = wires_deque[remove_ind]
    
    del wires_deque[remove_ind]
    
    list_one.append(a[0])
    list_two.append(a[1])

 

wires의 길이가 n-1이라고 했으니까 0부터 n-1까지 제거할 선분 remove_ind를 하나씩 돌아보는거임

 

deque에는 원소 하나 빼는건 없어서 원소 빼고 del을 이용해서 제거함

 

a에는 서로 연결된 node가 2개 들어간 [v1,v2] 형태로 되어 있어서 일단 list_one, list_two에 일단 나눠 넣어

 

while wires_deque != deque():
    
    c,d = wires_deque.popleft()
    
    if (c in list_one) or (d in list_one):
        
        list_one.append(c)
        list_one.append(d)
        
    elif (c in list_two) or (d in list_two):
        
        list_two.append(c)
        list_two.append(d)
        
    else:
        
        wires_deque.append([c,d])

다음에 wires_deque에는 선분 하나가 제거된 선분들의 집합이 들어가있는데

 

여기서 선분을 하나씩 뺀다음에 확인을 할거임

 

선분 하나 빼면 [c,d] 형태로 들어가 있을 건데

 

c나 d가 list_one에 들어가있다면 list_one에 맨 처음 들어간 a[0]랑 연결되어 있다는 뜻이므로 c,d를 list_one에 모두 넣어

 

여기서 모두 넣는건 c,d도 서로 연결되어 있기 때문에

 

반대로 c나 d가 list_two에 들어있다면… list_two에 모두 넣어

 

---------------------------------------------------------------------------------------------------------------------------------

 

 

 

예를 들어 위와 같이 1-2를 끊어서 1을 list_one, 2를 list_two에 먼저 넣었음

 

다음으로 2-3을 빼서 list_one과 list_two에 넣을건데

 

2나 3이 list_one에 들어가있다면 list_one에 있는 node들과 연결되어 있는 것이고

 

list_two에 있다면 list_two의 node와 연결되어 있다는 것임

 

위 그림처럼 2나 3이 list_two에 들어가있어서 list_two의 node들과 연결되어 있다는거 확인가능

 

근데 c나 d가 list_two나 list_one 모두에 들어가 있지 않은 경우가 있음

 

 

위와 같이 3-4를 먼저 끊어서 list_one에 3을 넣고 list_two에 4를 넣은다음

 

while 반복문으로 들어가 1-2를 빼서 확인을 할건데

 

1-2는 3에 들어가야함에도 불구하고

 

현재 list_one, list_two 어디에도 들어가있지 않아서 컴퓨터 입장에서는 어디에 연결되어 있는지 확인이 불가능함

 

그래서 이런 경우 else:로 처리해서 일단 wires_deque의 오른쪽에 다시 넣고 while 반복문을 다시 처리하도록 만들어

 

while 반복문은 while의 모든 원소를 두 집단으로 나눌때까지 반복할거임

 

---------------------------------------------------------------------------------------------------------------------------------

 

list_one = set(list_one)
list_two = set(list_two)

len_one = len(list_one)
len_two = len(list_two)

diff_len = abs(len_one - len_two)

 

근데 이제 node가 중복되어 들어가있기때문에 set을 이용해서 중복을 제거하고 길이를 구한다

 

이의 차이의 절댓값을 구한다

 

    if diff_len == 0:

        return 0

    elif remove_ind == 0:

        answer = diff_len

    elif diff_len < answer:

        answer = diff_len

    wires_deque = deque(wires)

    list_one = []

    list_two = []

return answer

 

시간을 줄이기 위해서 두 길이의 차이가 0이 되면 이게 최솟값이니까 바로 0을 return하면 됨

 

0이 아닌경우는 min값을 반복적으로 계속 저장해두는것

 

그리고 wires_deque랑 list_one,lIst_two를 초기화하고 다시 반복문 수행

 

반복문 다 끝나고 나온 answer가 정답이 된다

 

 

6. 다른 풀이

 

다른 풀이중에 union find를 이용했다는 풀이 확인

 

https://deepdata.tistory.com/186

union find 알고리즘

 

def solution(n, wires):
    
    global uf
    
    answer = int(1e9)
    
    for i in range(n-1):
        
        uf = [-1 for _ in range(n+1)]
        
        tmp = [wires[x] for x in range(n-1) if x != i]
        
        for a,b in tmp:
            
            merge(a,b)
            
        v = [x for x in uf[1:] if x < 0]
        
        answer = min(answer, abs(v[0] - v[1]))
        
    return answer

 

answer = int(1e9)라고 한건 초기화시킨건데 엄청 큰 수로 아무거나 초기화시킨것 같고

 

wires의 길이는 n-1이니까 for문에서 range(n-1)해서 0부터 n-2까지 도는건데

 

먼저 uf에 -1을 n개 넣는거임 uf=[-1,-1,...,-1]

 

node가 n개니까 그런것 같고

 

--------------------------------------------------------------------------------------------------

 

tmp=[wires[x]~]한건 x != i이면 wires[x]를 집어넣는데.. 이건 선분 하나 끊어서 tmp에 새로 집어넣는거임

 

for문을 이용해서 0번부터 n-1번까지 하나씩 잘라서 tmp에 넣어서 확인을 해보는거

 

그 다음 하나 선분 끊은 tmp에서 하나씩 빼서 merge(a,b)를 하는데… union알고리즘이겠지?

 

def merge(a,b):
    
    global uf
    
    pa = find(a)
    pb = find(b)
    
    if pa == pb:
        
        return
        
    uf[pa] += uf[pb]
    
    uf[pb] = pa

pa,pb가 아마 a,b의 부모 node를 말하는듯?

 

먼저 a,b의 부모 node를 find()함수를 이용해서 찾는가보다

 

def find(a):

    global uf
    
    if uf[a] < 0:
        
        return a
        
    uf[a] = find(uf[a])
    
    return uf[a]

이게 이제 node a의 부모 node를 찾는건데

 

uf[a]가 음수이면 a의 부모 node가 a라고 보고 a를 return하는듯

 

예를 들어서 생각을 해보자…

 

 

[1,2],[2,3],[3,4]에서 [1,2]를 끊은 경우 생각해보면…

 

처음에 uf = [-1,-1,-1,-1,-1]로 하는건 아무것도 연결이 안된 상태

 

tmp에는 [2,3],[3,4]가 들어가있음

 

for문에 먼저 a=2,b=3이 들어갈거임

 

def find(a):
    
    global uf
    
    if uf[a] < 0:
        
        return a
        
    uf[a] = find(uf[a])
    
    return uf[a]
    
def merge(a,b):
    
    global uf
    
    pa = find(a)
    pb = find(b)

 

merge(a,b)로 union을 하는데… find알고리즘으로 2와 3의 부모 node를 찾을건데

 

아무것도 연결이 안된 상태인 uf = [-1,-1,-1,-1,-1]라서 uf[a]가 음수니까 find(2)=2, find(3)=3이겠지…

 

pa=2이고 pb=3일거임.. 실제로 아무것도 연결이 안된 상태에서 부모 node는 2이고 3이니까...

 

if pa == pb:
    return
    
uf[pa] += uf[pb]

uf[pb] = pa

 

부모 node가 서로 다르니까 uf[pa]에 uf[pb]를 더해서 uf[2]=-1이고 uf[pb]=-1이니까 uf = [-1,-1,-2,-1,-1]이고… uf[pb]에 pa=2를 넣으니까…

 

uf = [-1,-1,-2,2,-1]로 바꿀거임

 

이게 무엇이냐… 3이 2에 연결되어 있다는 뜻임

 

 

[2,3]이 들어가서 union을 해서 연결이 된거니까 이렇게 바뀐거임

 

다음 a=3,b=4가 들어갈거임

 

그러면 union 알고리즘에 의해 find 알고리즘부터 시작해서… a=3의 부모 node와 a=4의 부모 node를 찾을거임…

 

현재 보면 알겠지만 a=3의 부모 node는 2이고 a=4의 부모 node는 자기 자신인 4임

 

실제로 find 알고리즘이 재귀적으로 작동해서 find(3)을 하면 uf[3]=2로 양수니까 find(2)가 작동해서 uf[2]=-2니까 2를 내놓음

 

def find(a):
    
    global uf
    
    if uf[a] < 0:
        
        return a
        
    uf[a] = find(uf[a])
    
    return uf[a]

 

실제로 위에서 개념설명한 그대로 재귀적으로 작동하는거 확인 가능

 

아무튼 a=3의 부모 node인 2와 a=4의 부모 node인 4를 내놓을거

 

pa=2, pb=4

 

def merge(a,b):
    
    global uf
    
    pa = find(a)
    pb = find(b)
    
    if pa == pb:
        return
        
    uf[pa] += uf[pb]
    
    uf[pb] = pa

 

pa와 pb가 다르니까… uf[2]=-2에 uf[4]=-1을 더해서 uf = [-1,-1,-3,2,-1]이 될거고… uf[4]=pa=2를 넣어서 node 4의 부모 node가 2임을 가리키도록 만든다

 

 

여기까지 하면 느낀점이… node 수는 4개인데 왜 uf 원소의 수는 5개인가???

 

uf에 4개 들어가면 uf[4]는 불가능하니까… 이런 점도 고려했나보네..

 

아무튼 for a,b in tmp:를 돌면 위와 같이 새로 연결이 된다는거

 

    v = [x for x in uf[1:] if x < 0]

    answer = min(answer, abs(v[0] - v[1]))

return answer

 

for문을 돌고나서… v에 집어넣는데.. uf = [-1,-1,-3,2,2]에서… uf[1:]=[-1,-3,2,2]에서… x<0인 부분은 -1과 -3이네…

 

이 -1과 -3이 무슨뜻이냐…

 

지금까지 잘 따라왔다면… 연결이 되면 가장 작은 node값을 가지는 부모 node에 -1씩 더해졌거든

 

-1은 첫번째 집합에는 1개의 node가 있다는 뜻이고… -3은 두번째 집합에는 3개의 node가 있다는 뜻…

 

7. 되돌아보기

 

그래프 문제만 보면 도망치는데 상당히 생각을 잘 했다

 

두 집합으로 나눌 생각을 했다는점

 

집합끼리 연결된 그래프 node들을 어떻게 찾는가?

 

연결된 선분 리스트 내 node가 존재하면 연결된 것이라는 점을 이용해서 하나하나 합쳤다는 점

 

union find 배우긴 했는데... 알고리즘은 쉬운데 풀이가 상당히 고난이도네 흐음