[Python] 프로그래머스 - 전력망을 둘로 나누기 파이썬 풀이

나의 첫 풀이

예상

하지만 코드로 옮기는 순간 예상과는 조금 다른...

 

1. 연결 상태를 이차원 배열로 받는다.
2. 연결 하나를 끊어서(이차원 배열 중 하나를 0으로 만들어서)
3. 분리된 노드의 개수를 탐색하고, 차이값을 비교한다.

DFS로 풀어보려고 stack도 써보고 visited도 써봤으나 문제점이 있었다.

1. 어떻게 끊는가?
2. 끊긴 것 중 연결된 노드를 탐색해서 개수를 찾는가?
3. 개수를 어떻게 비교하는가?

세 가지 부분에서 풀이가 막혀서 고민하다가 다른 사람의 도움을 얻기로 마음 먹었다.
내가 고민하던 흔적은 다음과 같다. (부끄럽지만 남겨두겠다)

def solution(n, wires):
    answer = -1
    
    linked = [[0] * (n+1) for _ in range(n+1)]
    
    # 연결 되어 있는 배열 만들기
    for links in wires:
        linked[links[0]][links[1]] = linked[links[1]][links[0]] = 1
    
    # '한 쌍'을 선택해서 연결을 끊기
    for cut in wires:
        # 자른다.
        linked[cut[0]][cut[1]] = 0
        stack= [cut[0],cut[1]]
        visited = [[0] * (n+1) for _ in range(n+1)]
        node1 = 0
        node2 = 0 
        # 이제 끊긴 부분의 node 개수를 비교한다. (연결되어있는 부분의 node 개수 비교)
        while stack:
            node = stack.pop()
            for i in range(1,n+1):
                for j in range(1, n+1):
                    if linked[i][j] == 1 and not visited[i][j]:
                        # 방문처리해주고
                        visited[i][j] = visited[j][i] = 1
                        stack.append([i,j])
                        node1 += 1
                    elif 
                        node2 +=1
        print(node1, node2)

        
    return answer

다른 이의 소중한 풀이에서 해답을 찾았다! (감사합니다 )
https://jeongmin.tistory.com/5

[프로그래머스 Level 2] 전력망을 둘로 나누기 - 파이썬(Python)

풀이를 하며 중점적으로 기억할 것은

1. 트리 자료로 연결 받았을 때 연결을 나타내는 방식(잊었던 나의 기억)
2. bfs 로 어떻게 처리해줄거야! (방문 배열 만들고 , 처리하고, 덱에 넣어주고, 처리해줄 계산하고 while q로 돌려!)
3. 연결 어떻게 끊을거야! (리무브 다시해주고, res로 끊어진 값들의 연결된 노드 값구해주고 다시붙여놓을거야)

이 풀이다 이풀이! 내가 원했던!!!!

이 과정을 완수하면 비로소 결과를 얻을 수 있다. 정말 값지다!

이런 사고 과정을 한 번에 할 수 있다면 코테가 두렵지 않을 것이다.

창조의 첫 걸음은 모방이 아닌가? 그들의 사고방식을 마구 흡수하고 연습해서 성장해야겠다.

from collections import deque

def solution(n, wires):
    
    graph = [[] for _ in range(n+1) ]
    
    #연결 리스트 완!
    for a,b in wires:
        graph[a].append(b)
        graph[b].append(a)
        
    def bfs(start):
        visited = [0] * (n+1)
        q = deque([start])
        # 방문처리
        visited[start] = 1
        cnt  = 1
        while q:
            # s를 빼준다.
            s = q.popleft()
            # s와 연결된 값들
            for i in graph[s]:
                if not visited[i]:
                    q.append(i)
                    visited[i] = 1
                    cnt += 1
        return cnt
    
    # 최대의 수 (노드 개수임)
    res = n 
    for a,b in wires:
        graph[a].remove(b)
        graph[b].remove(a)
        
        #res는 최솟값. b랑 a는 연결해제됐으니 각각 연결 노드 구할 수 있음. 그중 최솟값
        res = min(abs(bfs(a)- bfs(b)), res)
        
        #다시 이어붙여주기
        graph[a].append(b)
        graph[b].append(a)
        
    return res