[Python - 프로그래머스] 코딩테스트 연습 > 완전탐색 > 전력망을 둘로 나누기

[Python - 프로그래머스] 코딩테스트 연습 > 완전탐색 > 전력망을 둘로 나누기

 

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

---

 

Solution

 

import copy
 
def connect(temp, k) :
    global c
    c.append(k)
    tk = temp[k]
    tk = list(set(tk) - set(c))
    return [connect(temp, i) for i in tk]
 
def solution(n, wires):
    global c
    temp = dict()
    for i in range(1,n+1) :
        temp[i] = list()
    for i in wires :
        temp[i[0]].append(i[1])
        temp[i[1]].append(i[0])
 
    # 하나씩 끊으면서 개수 확인
    cnt = list()
    for i in wires : 
        temp_ = copy.deepcopy(temp)
        temp_[i[0]].remove(i[1])
        temp_[i[1]].remove(i[0])
 
        c = list()
        connect(temp_,i[0])
        cnt.append(len(c))
    
    
    return min([abs(n-i-i) for i in cnt])

 

temp에 연결된 원소들을 dictionary 형태로 만들어준다.

예로 아래에 입출력 예 #3에 대한 temp의 결과는 다음과 같다.

 

 

세 번째 예시에 대한 temp 결과

 

 

connect function은 temp와 k를 입력으로 받아, k번 송전탑과 연결된 모든 송전탑을 찾아준다.

결과는 c에 담긴다.

 

[1, 2] 부터 전선을 하나 씩 끊으면서 결과를 확인하면 다음과 같다.

 

 

temp_에 temp를 deepcopy하고, remove()를 통해 끊어진 부분을 업데이트한다.

(deepcopy()하지  않으면 temp에 있는 값도 같이 지워진다.)

 

1과 2를 끊으면 1과 연결된 송전탑은 1 뿐이다.

 

2와 7을 끊으면 2와 연결된 송전탑은 2와 1이다.

 

3과 7을 끊으면 3과 연결된 송전탑은 3, 4, 5이다.

 

...

 

끊어진 송전탑 둘 중에 하나랑 연결된 송전탑 개수만 확인하면, 나머지 송전탑과 연결된 개수는 처음 주어진 n에서 빼면 된다.

 

---

 

다른 사람의 풀이

 

 

for문 안에 wires[i+1:] + wires[:i] 의 의미는 i번째 wires를 끊었을 때 연결 정보이다.

 

 

s = set(sub[0])

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

 

에서 s는 sub[0]과 연결된 모든 노드를 담는다.

2번째 줄을 풀어서 써보면 다음과 같다. 

 

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

 

[3, 7] 전선을 끊는다는 가정 하에 중간과정을 print해보면 다음과 같다.

 

 

set(v) & s는 intersetction과 같은 의미이며, 예시는 다음과 같다.

 

 

if문 안에 condition으로 들어가 intersection이 있으면 True, 없으면 False를 return한다.

즉, s와 v에 겹치는게 있으면 v를 s에 update하면서 결국 sub[0]과 연결된 모든 송전탑을 update하게 된다.

 

 

이중 for문인 이유는 [4, 5] 연결을 끊을 때를 확인해 보면 알 수 있다.

[4, 5]를 제외하므로 sub은 [[6, 7], [1, 2], [2, 7], [3, 7], [3, 4]] 이다.

 

[s.update(v) for _ in sub for v in sub if set(v) & s] 안에 내용을 매 for문마다 print해보면 다음과 같다.

 

 

[6, 7] [6, 7] 은 _와 v를 print한거고, {6, 7}은 s를 print한 과정이다.

 

v가 처음 [1, 2]일 때는 s에 {6, 7}만 있어서 교집합이 없었다.

그러나 두 번째 [1, 2]에서는 s에 2가 있었기 때문에 1이 추가된다.