[프로그래머스 level2 9주차_전략망을 둘로 나누기] find, union 활용법 & dfs 활용법

해결해야하는 문제는 다음과 같았다.

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

코딩테스트 연습 - 9주차

 

이 문제는 두 가지 방법으로 풀어보았다.

1. find_union 활용

2. dfs 활용

 

첫번째 시도 했던 아이디어는 다음과 같다.

 

이는 부모를 찾고 union 해주는 아이디어에서 출발하였다.

하나의 tree를 이루는 원소들에서 하나의 연결선을 자르게 된다면 두 개의 root가 생기게 될 것이므로,

모든 연결선을 하나씩 끊어가며

root 정보를 저장할 parent 배열을 생성하여 root 정보를 찾고

root 정보에 해당하는 두 개의 원소의 차를 구하면서

최소가 되는 차를 찾도록 하였다.

 

 

아이디어를 바탕으로 작성한 코드는 다음과 같다.

(첫 번째 시도) find_parent, union_parent 찾기_실패!

def find_parent(parent,x):
    if parent[x] != x :
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b :
        parent[b]=a
    else :
        parent[a] = b

def solution(n, wires):
    answer = n+1

    for i in range(n-1):
        remain_wires = wires[:i] + wires[i+1:]
        parent = [p for p in range(n+1)]

        for rw_a,rw_b in remain_wires :
            union_parent(parent,rw_a,rw_b)   
            
        if answer > abs(2*parent.count(parent[1])-n) :
            answer = abs(2*parent.count(parent[1])-n)

    return answer

 

하지만 이렇게 구현하게 되는 경우, 4가지 테스트 케이스만 통과하게 된다.

 

 

 

+++ find, union 찾는 것을 조금 더 보완하여 성공하도록 하였다!!

2차시도로 문제해결을 한 뒤, 실패이유에 대해 생각해보니,

들어오는 wires가 작은 원소 순서대로 들어오지 않는 경우 문제가 발생할 수 있다는 것이었다.

wires가 [[1, 2], [2, 7], [3, 7], [3, 4], [4, 5], [6, 7]] 과 같이 오름차순형태가 아닌,

작은 값을 root value로 갖도록 구현하였기 때문에 완전히 순서가 뒤죽박죽인 경우, 꼬일 수 있을 것 같다고 생각하였다.

따라서 모든 끊어지지 않은 송전탑 edges 에 대해 union_parent을 해준 후, 모든 송전탑에 대해 find_parent를 해주어, 최종적으로 갱신해줄 수 있도록 하였다.

 

(첫 번째 시도) find_parent, union_parent 찾기 보완_ 성공!

def find_parent(parent,x):
    if parent[x] != x :
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b :
        parent[b]=a
    else :
        parent[a] = b

def solution(n, wires):
    answer = n+1

    for i in range(n-1):
        remain_wires = wires[:i] + wires[i+1:]
        parent = [p for p in range(n+1)]

        for rw_a,rw_b in remain_wires :
            union_parent(parent,rw_a,rw_b)   
        
        
        ## 추가한부분
        for j in range(1,n+1):
            find_parent(parent,j)
            
        if answer > abs(2*parent.count(parent[1])-n) :
            answer = abs(2*parent.count(parent[1])-n)

    return answer

 

 

 

 

 

 

2번째 시도 했던 방법은 dfs를 활용하였다.

 

아이디어를 바탕으로 작성했던 코드는 다음과 같다.

(두번째시도) dfs 활용하기_성공!

def dfs(wire_info,start,n):
    stack = [start]
    visited = [0]*(n+1)
    count = 0
    while stack :
        x = stack.pop()
        visited[x] = 1
        count += 1
        for w in wire_info[x] :
            if not visited[w] :
                stack.append(w)
    return count


def solution(n,wires):
    answer = n+1
    cut_wires = list(wires)
    while cut_wires:
        cut_wire_a, cut_wire_b = cut_wires.pop()
        wire_info = [[] for _ in range(n+1)]
        for a,b in wires :
            if a == cut_wire_a and b == cut_wire_b :
                continue
            wire_info[a].append(b)
            wire_info[b].append(a)
        differ = abs(2*(dfs(wire_info,cut_wire_a,n))-n)
        if answer > differ:
            answer = differ
    return answer

 

 

첫번째 아이디어로 실패한 후, 두 번째 아이디어로 해결한 뒤, 첫번째 아이디어의 문제점에 대해서 알아볼 수 있었던 값진 시간이었다.⏱