프로그래머스 - 코딩테스트 고득점 Kit - 완전탐색 - 전력망을 둘로 나누기(python)

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

프로그래머스

문제를 이해하셨다는 전제하에 코드 설명 들어가겠습니다.

채점결과

생각한 알고리즘

* 내가 생각한 알고리즘은 dfs와 유사하다. 근데 dfs보다는 비효율적이다.

 

1. 에지(선)을 for문을 돌려가며 끊어본다.

2. 그 상태에서 1을 시작으로 하는 전력망(그래프)가 있는지 확인한다.

1) check_in 이라는 함수를 이용해 전력망이 더 커질 수 있는지 확인한다.

- 있다면 계속 이어서 저장하면 되고 큐 형태와 유사하게 저장된다.

- 없다면 (그동안 담긴 save의 크기와 save에 담기지 않은 노드의 개수의 차) 제곱을 result에 담는다.

3. (result 값 중에서 가장 작은값)의 양의 제곱근을 출력한다.

 

**자세한 설명은 to be continue...

import copy
#2 - 1) check_in 이라는 함수를 이용해 전력망이 더 커질 수 있는지 확인한다.
def check_in(wires_tmp, save, st):
    for i in range(len(wires_tmp)):
        if save[st] in wires_tmp[i]:
            return i, st
    if st + 1 == len(save): return -1, st
    return check_in(wires_tmp, save, st + 1)

def solution(n, wires):
    wires_tmp = copy.deepcopy(wires)
    result = []
    #1. 에지(선)을 for문을 돌려가며 끊어본다.
    for i in range(len(wires)):
        wires_tmp.pop(i)
        #2. 그 상태에서 1을 시작으로 하는 전력망(그래프)가 있는지 확인한다.
        save = [1]
        #passed = []
        while True:
            c, st = check_in(wires_tmp, save, 0)
            # 있다면 계속 이어서 저장하면 되고 큐 형태와 유사하게 저장된다.
            if c >= 0:
                #passed.append(save[0])
                tmp = copy.deepcopy(wires_tmp[c])
                tmp.pop(tmp.index(save[st]))
                save = tmp + save
                wires_tmp.pop(c)
            # 없다면 (그동안 담긴 save의 크기와 save에 담기지 않은 노드의 개수의 차) 제곱을 result에 담는다.
            else:
                a = n - len(save)
                b = len(save)
                result.append((a - b) ** 2)
                break
        wires_tmp = copy.deepcopy(wires)
        
 # 3. (result 값 중에서 가장 작은값)의 양의 제곱근을 출력한다.       
    return int(min(result) ** (1 / 2))