[프로그래머스] 전력망을 둘로 나누기. 여러가지 풀이

내 코드 (입접 행렬)

def solution(N, wires):
    T = [[False]*(N+1) for _ in range(N+1)]
    for u,v in wires:
        T[u][v] = True
        T[v][u] = True
        
    def dfs(V):
        visited=[False]*(N+1)
        visited[V]=True
        stk=[V]
        while stk:
            v = stk.pop()
            for i in range(1,N+1):
                if(T[v][i]==True and not visited[i]):
                    visited[i]=True
                    stk.append(i)
        result = sum(1 for x in visited if x)
        return result
    
    mn = N
    for u,v in wires:
        T[u][v] = False
        T[v][u] = False
        visit = dfs(1)
        temp = abs(N-2*visit)
        mn = min(mn, temp)
        T[u][v] = True
        T[v][u] = True
        
    return mn

• 전선이 끊어진 경우를 선형적으로 탐색하고, 그 안에서 랜덤하게 V를 골라 그래프 전체를 순회한다.
• 문제의 조건에서 처음에 하나의 트리로 구성돼 있다고 했기 때문에 다른쪽 트리는 탐색할 필요 없이 N에서 현재 트리의 전신주 갯수를 빼주기만 하면 된다.
• 이렇게 하면 탐색 시간은 최악의 경우에 N*(N-1) 정도 될 것이다. (항상 큰 트리를 고르는 경우)
• 따라서 시간복잡도는 O(N^2) 이지만 N이 100 이하이므로 완전 탐색 해볼만 하다.

조금 다른 접근(인접 리스트)

• wire를 끊는 걸 구현하는 방법 중에, 특정 노드를 방문 처리하고 들어가는 방법도 있었다.
• 이렇게 하면 DFS시 시작 노드에서 방문처리된 노드로 가는 wire를 타지 않을 것이기 때문에 wire를 끊는 것과 같은 효과가 있다.
• 이 경우 그래프를 인접행렬이 아닌 인접 리스트로도 표현할 수 있는 장점이 있다.

def solution(n, wires):
    G = {e:[] for e in range(1,n+1)}
    for v, u in wires:
        G[v].append(u)
        G[u].append(v)
        
    def dfs(V, cut):
        visited = [False]*(n+1)
        visited[V] = True
        visited[cut] = True
        stk=[V]
        while(stk):
            v = stk.pop()
            for nextV in G[v]:
                if(not visited[nextV]):
                    visited[nextV] = True
                    stk.append(nextV)
        return sum(1 for x in visited if x)-1
        
    mn = n
    for v1,v2 in wires:
        temp = abs(n-2*dfs(v1,v2))
        mn = min(mn, temp)
    return mn

• dfs는 재귀로 더 짧게 만들 수도 있다.

def solution(n, wires):
    G = {e:[] for e in range(1,n+1)}
    for v, u in wires:
        G[v].append(u)
        G[u].append(v)
        
    def dfs(V,cut):
        visited[V] = True
        visited[cut] = True
        return 1+sum(dfs(u,0) for u in G[V] if not visited[u])
        
    mn = n
    for v1,v2 in wires:
        visited=[False]*(n+1)
        temp = abs(n-2*dfs(v1,v2))
        mn = min(mn, temp)
    return mn

• 재귀 dfs에서 return시 sum에서 +1을 한 이유는, 최종 방문한 노드의 수가 카운트해 반환하는 함수이기 때문이다.
• 반면에 stack으로 구현한 dfs는 반환시 visited한 노드 수를 세기 때문에 진짜 방문하지 않은 cut 노드는 빼고 세야 한다. (-1)

괴수 코드 (간선 리스트)

• 이거 보여주려고 어그로 끌었다.

def solution(n, wires):
    ans = n
    for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):
        s = set(sub[0])
        [s.update(v) for _ in sub for v in sub if set(v) & s]
        ans = min(ans, abs(2 * len(s) - n))
    return ans

• 5번째 줄이 핵심인데 좀 더 풀어보면 아래 식을 한 줄로 쓰기위해 list comprehension을 쓴 것이다.

for _ in sub: 
	for v in sub: 
		if set(v) & s:
			s.update(v) 

코드 읽기

• wire를 하나씩 빼기 위해 wires[i]+wires[i+1:] 를 했다.
• 따라서 sub은 wires중 하나가 빠진 wire리스트다. ex) [[2, 3], [3, 4], [4, 5], …]
• s = set(sub[0]) 을 함으로써, 첫번째 wire가 포함하는 두 전신주를 모두 visit 처리 한다.
  • s는 이후로 visit list처럼 쓰인다.
• set(v) & s 로 s에 포함된 전신주에서 더 뻗어나갈 수 있는 와이어인지 검사한다. 뻗어나갈 수 있으면 결과가 있는 set가 반환될 것이고, 이 때 v 값들을 s에 넣어준다.
  • 위 과정을 모든 wire에 대해 반복한다.
  • 그 과정을 sub의 갯수만큼 반복하는 이유는 최악의 경우 (처음 고른 v (sub[0]) 이 연결된 트리에 맨 마지막에 있고, 한줄로 연결된 트리인 경우)더라도 모든 wire들이 연결되는 것을 보장하기 위해서 반복하는 것이다.

고찰

• 위에서 for _ in sub 를 하는 건 벨만포드와 비슷한 면이 있다.
  • 벨만포드는 모든 지점에 대한 최단 거리를 구하기 위해 연결된 곳까지(dist가 inf가 아님)의 최단 거리를 구한다.
  • 이후에 모든 vertex에 대해 다시한번 최단거리를 구하는데, 이 때 이전에 갱신된 거리로 인해 연결이 점점 늘어난다. (inf가 아닌 노드가 늘어남)
  • 최악의 경우(시작 노드에서 모든 간선을 거쳐야 도달 한수 있는 노드까지 의 거리)까지 업데이트 하기 위해 나올 수 있는 최대 간선(V-1) 만큼 반복한다.
• 위와 같은 방식을 집합 확장(Set Expansion)이라고 한다고 한다.
  • 그런데 이게 dp는 아니다. 최적 부분 구조가 아니기 때문이다.
  • 아이디어의 일부만 벨만포드와 비슷하다.
  • 집확 확장은 MST(크루스칼, 프림) 알고리즘에 담겨있다.

유니온 파인드

• 집합하면 생각나는, union-find로도 풀 수 있다.

uf = []

def find(a):
    global uf
    if uf[a] < 0: return a
    uf[a] = find(uf[a])
    return uf[a]

def merge(a, b):
    global uf
    pa = find(a)
    pb = find(b)
    if pa == pb: return
    uf[pa] += uf[pb]
    uf[pb] = pa

def solution(n, wires):
    global uf
    answer = int(1e9)
    k = len(wires)
    for i in range(k):
        uf = [-1 for _ in range(n+1)]
        tmp = [wires[x] for x in range(k) if x != i]
        for a, b in tmp: merge(a, b)
        v = [x for x in uf[1:] if x < 0]
        answer = min(answer, abs(v[0]-v[1]))

    return answer

• 유니온 파인드 공부하기 좋은 코드다. 다른 포스팅에서 다뤄봐야겠다.