python 코딩테스트 - 프로그래머스 전력망을 둘로 나누기

출처 : 프로그래머스

처음 든 생각

- 이건 무조건 DFS를 써야된다.

- 하나가 끊어진 모든 경우를 탐색하면서 DFS를 해서 차이를 구하면 되겠다.

 

나의 답

def solution(n, wires):
    answer = n
    
    def dfs(g,v,s):
        v[s] = True
        for k in g[s]:
            if v[k] == False:
                dfs(g,v,k)
            
    for i in range(len(wires)):
        a,b = wires[i]
        wires[i] = [0,0]
        g = [[] for _ in range(n+1)]
        v = [False for _ in range(n+1)]
        for j in range(n-1):
            x,y = wires[j]
            if x > 0:
                if y not in g[x]:
                    g[x].append(y)
                if x not in g[y]:
                    g[y].append(x)
        wires[i] = [a,b]
        
        for i in range(n+1):
            if g[i]:
                dfs(g,v,i)
                break
                
        count = 0
        for i in v:
            if i == True:
                count += 1
        count2 = n - count
        diff = max(count-count2, count2-count)
        
        answer = min(answer,diff)
            
    return answer

DFS의 코드를 작성했지만 먼저 흐름을 파악하기 위해 아래의 반복문을 먼저 작성했다.

 

wires에서 하나씩 없애주는 과정을 하기 위한 반복문이다.

기존의 값을 임시로 저장하고 remove 하는 방식이 아니라 0,0으로 대치하는 방식을 택했다.

 

다음으로, 해당 문제는 각 노드별 연결 포인트를 그래프로 표시해주는 것이 아니기에 DFS를 하기 위해서 스스로 그래프를 구현해야했다.

g의 빈 배열을 노드 개수+1 만큼 펼쳤다. (인덱스가 아니라 노드 번호에 맞춰서 바로 참조할 수 있도록)

 

그 다음 wires를 다시 반복문으로 돌면서 연결된 노드 들을 g에 추가해준다. 0인 부분은 끊어진 연결이기 때문에 그 부분만 조건으로 걸어주면 된다. 그렇게 하나의 연결이 끊긴 그래프가 완성 되었으므로 wires는 다시 원상복구를 시켜준다.

 

이제 이 그래프를 가지고 DFS를 할 것이다.

DFS는 그래프, 방문 배열, 시작 노드 3개의 인자를 받게 한다.

그래프에 만약 연결된 노드가 없으면 DFS를 시작할 수 없기 때문에 그래프에서 하나라도 연결된 노드가 있다는 것을 확인하고 DFS를 할 수 있도록 구성했다.

 

DFS의 순서는 시작 노드를 방문하고 그 다음 그래프에서 그 노드에 연결된 노드들을 반복문으로 돌면서 재귀적으로 동작하는 것이다.

-> 이건 매우매우 중요하므로 암기해놓자.

 

DFS를 하게 되면 연결되어있는 하나의 덩어리가 구성하고 있는 노드들에 대해 v리스트에 True로 찍혀있을 것이다. 그래서 True인 노드들을 세주면 하나의 덩어리가 가지고 있는 노드 수가 되고 다른 덩어리는 전체에서 빼주면 되므로 (무조건 2 덩어리) 2개의 차이의 절댓값을 구하여 answer에 할당한다.

---

이 문제에서 조금 까다로웠던 점은 그래프를 직접 만들면서 인덱싱을 실수한 것, 그리고 DFS 함수에 인자를 어떤 것으로 줘야 하는지 고민이 되었고 반복문에 재귀까지 시간 복잡도가 조금 빡세보이지만 최대한 병렬적으로 처리하여 시간복잡도를 낮추어 테스트 케이스를 한 번에 통과할 수 있었다.