[프로그래머스] 전력망을 둘로 나누기 (Python3)

https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3 

코딩테스트 연습 - 9주차_전력망을 둘로 나누기

adj=[[] for _ in range(101)]
visit=[]

def dfs(i):
    visit[i]=True;
    for t in adj[i]:
        if not visit[t]:
            dfs(t)

def check(n, visit):
    cnt=0
    for i in range(1,n+1):
        if visit[i]:
            cnt+=1
    return cnt

def solution(n, wires):
    global visit
    answer = 100
    for wire in wires:
        adj[wire[0]].append(wire[1])
        adj[wire[1]].append(wire[0])
    for i in range(0,n-1):
        a=wires[i][0]
        b=wires[i][1]
        adj[a].remove(b)
        adj[b].remove(a)
        visit=[False]*(n+1)
        dfs(a)
        a_cnt=check(n, visit)
        visit=[False]*(n+1)
        dfs(b)
        b_cnt=check(n, visit)
        answer=min(answer, abs(a_cnt-b_cnt))
        adj[a].append(b)
        adj[b].append(a)
    return answer

죠..큼.. 더럽게 짠 듯..

 

완전탐색+DFS(아니면 BFS) 문제이다.

 

wires 중 자를 wire를 선택하고, 자른 wire의 양 끝을 DFS 돌려줘서 각자 이어진 송전탑 갯수를 구해준다.

이때 자른 wire를 선택할 때 이웃한 노드를 나타내는 adj 배열에서 서로를 제외시켜줘야 한다. (remove 함수 이용)

그래야 DFS 돌릴 때 잘라져서 더이상 이웃하지 않는 애들을 방문하지 않을 수 있다.

각자 이어진 송전탑 갯수는 visit 배열에서 true인 것의 수를 세서 구한다.

 

다른 분들의 코드를 보니 check[][] 배열을 이용해서, 서로 연결 여부를 나타낼 수 있다. (check[a][b], check[b][a])

그리고 끊어진 wire이면 check[][]=false 하는 식으로 표시할 수 있다. 

BFS 방문을 해서, 이어진 송전탑 갯수를 구하는데, 이때 방문 조건은 "check[node][target], check[target][node] 가 모두 true 이면서, target이 미방문일 경우" 이다. 방문한 애들을 cnt+1 해줘서 송전탑 갯수를 구하면 된다.

BFS가 훨 명확하게 풀리는 것 같다.