프로그래머스_level2_전력망 둘로 나누기(python)

 5일 만에 풀었다.

원래 30분~1시간 정도 고민해보고 안 떠오르면 구글링을 하는 편인데

level2에 높은 정답률에 문제에서 무슨 알고리즘인까지 알려줘서 구글링을 하기에는 존심이 살짝 상해.. 할 것 없을 때 5분 씩 고민해봤다.

 

# 접근

 크지 않은 n의크기 wires의 길이는 n -1이라고 문제에서 주어졌으니 bfs를하면 시간내에 풀 수 있다.

 

# 풀이 

 

1. wires를 차례대로 하나씩 받아서 graph를 만든다.

2. 연결돼 있는 전력망을 끊었을 때 둘의 차이를 어떻게 구할까 => 끊고자 하는 전력망을 타고가서 몇 개가 연결돼 있는지 확인한다.

3. 구한 개수를 이제 나머지 부분에서의 개수와 빼주면 된다. 끝~~~ 쉽죠잉 (이걸 왜 처음에는 생각을 못했지...)

 

# 코드

from collections import deque
def check(start, end, visited, graph):
    visited[start] = 1
    visited[end] = 1
    q = deque()
    q.append(end)
    cnt = 1
    while q:
        cur = q.popleft()
        for next in graph[cur]:
            if not visited[next]:
                visited[next] = 1
                cnt += 1
                q.append(next)
    return cnt

def solution(n, wires):
    answer = -1
    graph = [[] for _ in range(n+1)]
    for s, e in wires:
        graph[s].append(e)
        graph[e].append(s)
    answer = float("inf")
    for s,e in wires:
        visited = [0] * (n+1)
        res = check(s, e, visited, graph)
        alpha = abs(n - res)
        res = abs(res - alpha)
        answer = min(answer, res)
    return answer

 

# 회고

공부 많이 했다. 다 알고 있는 부분일 것이다. 조금만 침착해보자