전력망을 둘로 나누기

코딩테스트 연습 - 전력망을 둘로 나누기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 코드

def solution(n, wires):

    # 일단 9999로 시작

    answer = 9999

    # for문으로 전력망 하나씩 뺴주자

    for i in wires:

        new_wires = wires[:]

        new_wires.remove(i)

        #연결된 전력망 카운트 변수

        wires_count = 0

        # 이어져있는 전력망 딕셔너리로 만들어줌

        wires_dict = {}

        for i in new_wires:

            if i[0] not in wires_dict:

                wires_dict[i[0]] = [i[1]]

            else:

                wires_dict[i[0]].append(i[1])

            if i[1] not in wires_dict:

                wires_dict[i[1]] = [i[0]]

            else:

                wires_dict[i[1]].append(i[0])

        #print(wires_dict)

        #print(list(wires_dict.items())[0])

       

        # bfs를 위한 que 리스트 생성

        wires_que = []

        # 초기값을 넣어준다

        wires_que.append(list(wires_dict.items())[0])

        # 방문 확인 리스트 생성

        visit = [0]*(n+1)

        # while문으로 이어져있는 전력망개수를 찾아낸다

        while wires_que:

            x,y = wires_que.pop(0)

            wires_count += 1

            # 방문처리해줌

            visit[x] = 1

            # 방문하지 않았고 전력망 딕셔너리에 있으면 que리스트에 삽입

            for i in y:

                if visit[i] == 0 and i in wires_dict:

                    wires_que.append((i,wires_dict[i]))

       

        # 이어져있는 전력망 차이를 구함

        result_wires = abs(wires_count-(n-wires_count))

        # 기존 최솟값 보다 차이가 작으면 answer변환 시켜준다

        answer = min(answer, result_wires)

    #print(answer)

    return answer

solution(9, [[1,3],[2,3],[3,4],

             [4,5],[4,6],[4,7],

             [7,8],[7,9]])