[프로그래머스] Level2. 전력망을 둘로 나누기

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

 

프로그래머스

---

내일 AI tech 6기 코테가 있어서 네이버 측에서 올려준 프로그래밍 영역 자가진단 문제를 풀어봤다.

BFS로 문제를 풀었고 1시간 정도 걸렸다.

 

아직 프로그래머스가 익숙하지 않아서 디버깅을 못해서 애먹었다.

실제로 코테를 볼 때는 외부 IDE를 이용 금지니까 연습 해봐야지..

---

 

from collections import deque


def bfs(X, Y, n, graph):
    queue = deque()
    queue.append(X)
    visited1 = [False]*(n+1)
    num1, num2 = 1, 1 
    difference = 10000000000
    
    while queue:
        x = queue.popleft()
        if visited1[x] == False:
            visited1[x] = True
        for i in graph[x]:
            if visited1[i] == False:
                if i == Y:
                    continue
                else:
                    num1 += 1
                    visited1[i] = True
                    queue.append(i)
                    
    queue = deque()
    visited2 = [False]*(n+1)
    queue.append(Y)
    while queue:
        y = queue.popleft()
        if visited2[y] == False:
            visited2[y] = True
        for j in graph[y]:
            if visited2[j] == False:
                if j == X:
                    continue
                else:
                    num2 += 1
                    visited2[j] = True
                    queue.append(j)
        
    if num1 >= num2 and difference > (num1 - num2):
        difference = num1 - num2
    elif num1 < num2 and difference > (num2 - num1):
        difference = num2 - num1
    
    return difference


def solution(n, wires): # 송전탑 개수, 전선 정보
    answer = 100000000000000
    temp_answer = -1
    
    # make the graph
    graph = [[] for _ in range(n+1)]
    for i in range(len(wires)):
        a, b = wires[i][0], wires[i][1]
        graph[a].append(b)
        graph[b].append(a)
    
    for i, j in wires:
        temp_answer = bfs(i, j, n, graph)
        if answer > temp_answer:
            answer = temp_answer
    return answer