알고리즘 문제풀이:: 프로그래머스 Graph 전력망을 둘로 나누기

프로그래머스 풀이

문제리뷰

코딩테스트 고득점 Kit - 완전탐색 전력망을 둘로 나누기

그래프를 인접 행렬이나 인접 리스트로 구현할 줄 알고 그래프 탐색 (DFS / BFS)를 할 줄 아는지 물어보는 문제 같았다.

그래서 일단 DFS로 구현했는데 테스트케이스 2번 문제가 계속 틀려서 곰곰히 생각해보니

문제의 그래프는 undirect graph로 [1,2]나 [2,1]을 같게 처리해야 한다.

List로 구현해서 해당 부분이 중복된거 같아서 Set으로 처리했더니 해결됐다.

 

강의 내용

• vis( = ch) 변수에 끊고자 하는 노드를 1로 표시함
• 체크한 노드의 다른 한 쪽에 있는 노드를 DFS를 돌려 순회하여 개수를 셈
• 전체 개수에서 DFS를 돌릴 때 구한 개수를 이용해 두 구역의 송전탑 개수를 구함.

---

Python

전력망을 둘로 나누기

나는 직접 제거할 노드를 그래프 전체에서 뺐는데

강의에서는 간단하게 방문했다는 표시를 통해 처리한 점이 인상깊었음

vis = []
def DFS(k, g):
    global vis
    vis[k] = 1
    for v in g[k]:
        if vis[v] == 0:
            vis[v] = 1
            DFS(v, g)

def solution(n, wires):
    global vis
    graph = [set() for _ in range(n+1)]
    for i, wire in enumerate(wires):
        a, b = wire
        graph[a].add(b)
        graph[b].add(a)
    
    answer = 101
    for i in range(1, n+1):
        for v in graph[i]:
            vis = [0]*(n+1)
            
            graph[i].remove(v)
            graph[v].remove(i)
            DFS(i, graph)
            graph[i].add(v)
            graph[v].add(i)
            
            temp = vis.count(1) - vis.count(0) + 1
            if temp < 0: temp *= -1
            answer = min(temp, answer)
            
    return answer