[프로그래머스] 전력망을 둘로 나누기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 각 전력망을 하나씩 모두 끊어보며 상황별로 나눠지는 두 전력망의 개수 차이를 구하는 문제이다.

전력망을 두 그룹으로 나눴을 때 각 그룹에 있는 송전탑의 개수를 bfs 방법으로 구한다.

원래 전력망은 하나로 이어져있기 때문에 하나의 전선을 끊으면 무조건 두 그룹으로 나뉜다.

하여 한 번의 bfs으로 두 그룹의 송전탑 개수를 구할 수 있다.

두 그룹의 송전탑 개수의 차를 경우마다 저장하고 이 중 가장 작은 값을 구하면 된다.

 

1. 너비우선탐색을 할 때 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 각 경우마다 두 그룹의 송전탑 개수의 차를 저장할 리스트를 생성한다. cnt = list()
3. 송전탑의 처음 연결 상태를 그래프로 나타내기 위해 2차원 리스트를 생성하고 graph = list([] for _ in range(n + 1))
4. 전선을 하나씩 불러오며 for i in wires
5. 각 송전탑의 연결 상태를 저장한다. graph[i[0]].append(i[1])  graph[i[1]].append(i[0])
6. 전선의 개수만큼 반복하며 for i in range(len(wires))
7. 해당 인덱스에 위치한 전선을 끊는다. graph[wires[i][0]].remove(wires[i][1])
8. 이때 한 전선은 두 송전탑을 연결하므로 두 송전탑의 연결을 끊어준다. graph[wires[i][1]].remove(wires[i][0])
9. 분리된 두 그룹 중 한 그룹의 송전탑 연결 상태를 bfs으로 탐색하여 파악하는데, 이때 방문 기록을 저장할 리스트를 생성한다. result = list(False for _ in range(n + 1))
10. 송전탑 번호가 0은 없으므로 0에 해당하는 값을 바꿔준다. result[0] = True
11. 그래프의 연결 상황을 하나씩 불러오며 for j in graph
12. 만약 연결된 송전탑의 시작을 찾으면 if (len(j) != 0)
13. 해당 송전탑을 기준으로 연결된 한 그룹을 탐색한다. bfs(j)
14. 한 그룹의 연결 상황을 파악했으므로 종료한다. break
15. bfs 탐색을 하고 나면 한 그룹은 True로, 다른 그룹은 False로 나타날 것이다. 하여 True와 False의 개수를 세어 그 차이를 저장하면 된다. 여기서 0번 인덱스는 제외한 리스트에서 개수를 세어야 하며, 차이는 절댓값으로 저장한다. cnt.append(abs(result[1:].count(True) - result[1:].count(False)))
16. 다음 경우도 계속해서 확인하기 위해 그래프의 상태를 처음과 같이 복구한다. graph[wires[i][0]].append(wires[i][1])  graph[wires[i][1]].append(wires[i][0])
17. 모든 경우에 대한 결과를 파악했다면 차이가 가장 적은 것을 정답에 저장한다. answer = min(cnt)

반응형

3. 소스코드

from collections import deque

def solution(n, wires):
    answer = -1
    
    cnt = list()
    graph = list([] for _ in range(n + 1))
    for i in wires:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])

    for i in range(len(wires)):
        graph[wires[i][0]].remove(wires[i][1])
        graph[wires[i][1]].remove(wires[i][0])
        
        result = list(False for _ in range(n + 1))
        result[0] = True
        
        def bfs(start):
            queue = deque(start)

            while (queue):
                now = queue.popleft()
                result[now] = True
                for j in graph[now]:
                    if (not result[j]):
                        queue.append(j)
                        result[j] = True
        
        for j in graph:
            if (len(j) != 0):
                bfs(j)
                break

        cnt.append(abs(result[1:].count(True) - result[1:].count(False)))

        graph[wires[i][0]].append(wires[i][1])
        graph[wires[i][1]].append(wires[i][0])

    answer = min(cnt)
    return answer