(Python/LV2) 전력망을 둘로 나누기

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

풀이:

from collections import deque
def solution(n, wires):

    graph = [[] for _ in range(n+1)]
    n = res-1
    for u,v in wires:
        graph[u].append(v)
        graph[v].append(u)
    def bfs(start):
        visited = [0] * (n+1)
        q = deque([start])

        count , visited[start] = 1,1
        while q:
            node = q.popleft()
            for i in graph[node]:
                if not visited[i]:
                    visited[i] = 1
                    count +=1
                    q.append(i)
        return count
    for a, b in wires: # 한 곳 끊기
        graph[a].remove(b)
        graph[b].remove(a)
        res = min(abs(bfs(a)-bfs(b)), res)
        break
        # 복구
        graph[a].append(b)
        graph[b].append(a)

    return res







print(solution(9, [[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [4, 7], [7, 8], [7, 9]]))

 

 

 

graph = [[] for _ in range(n+1)]
res = n-1
for u,v in wires:
    graph[u].append(v)
    graph[v].append(u)

graph (n+1) >> 선은 1부터 시작하기때문에

res = n-1 >>> 점 1개만 연결되어있고 하나는 아무것도 안 연결 되어있으면 n-1개가 최댓값이다

 

 

for a, b in wires: # 한 곳 끊기
    graph[a].remove(b) # a > b 
    graph[b].remove(a) # b > a
	res = min(abs(bfs(a)-bfs(b)), res)
    # 복구
    graph[a].append(b)
    graph[b].append(a)

return res

 

 

 

이제 한 곳을 끊어야한다. 

만약 1번이랑 3번이 양쪽으로 연결되어있으면

1 > 3  , 3 > 1  방향 다 제거해주고

bfs(1), bfs(3) 을 해주면 1,3 과 연결된 점들 bfs 해서 리턴해준다 abs를 해줘야 절댓값 리턴

 

1,3b 로 bfs 돌리면 bfs에 1,3 양방향이 빠진상태다 다시 복구해준다.

 

 

def bfs(start):
    visited = [0] * (n+1)
    q = deque([start])

    count , visited[start] = 1,1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if not visited[i]:
                visited[i] = 1
                count +=1
                q.append(i)
    return count

계속 봐오던 bfs 실행해주면 된다.