[프로그래머스/파이썬] 전력망을 둘로 나누기 풀이 (dfs, 완전탐색, python)

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

(dfs, 완전 탐색, python)

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

 

1. 문제

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

---

 

2. 문제 해결 아이디어 

 

일단, 송전탑들은 모두 전선 하나씩으로 연결되어 있다.

그렇기에 전선을 한 개를 끊으면 전력망은 2개가 된다.

 

그렇기 때문에, 전선을 끊었을 때 A,B 두 개로 나눠진 전력망을

각각 DFS를 이용하여 연결된 전력망을 따라 송전탑의 개수를 구하면 된다.

**이때, dfs를 사용하기 위해 wires 배열을 그래프 구조로 새로 만들어줘야 한다.

**또한, 노드별 방문여부를 저장하는 배열을 한 개 만들어줘야 한다.

 

---

3. 코드

# False : 방문안함
# True : 방문함 
import sys

def dfs(v, graph, visited):
    count = 1
    visited[v] = True
    
    for node in graph[v]:
        if not visited[node]: # 해당 노드 방문 이력이 없다면
            count += dfs(node, graph, visited) #카운드 증가하면서, 연결된 곳 찾아가기
    return count

    
def solution(n, wires):
    answer = 999999
    # 인접 리스트를 저장하는 그래프를 생성하자
    graph = [[] for _ in range(n+1)] # index에 node-1번 노드와 연결된 노드가 저장되어있음 # 첫 번호는 무시때리기 (0번은 없으므로)
    
    for a, b in wires: # 각 인덱스 노드에 ,연결된 노드 번호를 추가한다.
        graph[a].append(b) # 나자신은 b와 연결
        graph[b].append(a) # 연결된 b는 나와 연결
    
    print(graph)
    
    # 간선을 한개씩 끊어가면서 테스트해보자.
    for i in range(len(wires)): # 연결된 와이어 개수만큼 반복
        # 반복처리 배열 생성, 0번은 무조건 True이다.
        visited = [False] * (n+1)
        visited[0] = True 
    
        a,b = wires[i] # 끊을 간선을 저장 [1,3]
        
        # 간선 a-b를 끊는다
        graph[a].remove(b)
        graph[b].remove(a)
        
        # a에서 dfs를 시작한다. 
        #그러면 끊어진 b 통로 전까지 dfs로 개수를 셀 것이다.
        leftNodeCount = dfs(a, graph, visited)
        
        # b에서 dfs를 시작한다.
        # 그러면 b~ 끝까지 진행할것. (a와 연결된곳을 제외하고)
        rightNodeCount = dfs(b,graph,visited)
        
        # 두개의 송전탑 개수의 차이(절대값)을 구하고, 최소값으로 갱신해주자.
        answer = min(answer, abs(leftNodeCount - rightNodeCount))
                     
        # 끊어둔 간선을 다시 연결해주자.
        graph[a].append(b) # a->b 연결
        graph[b].append(a) # b->a 연결

    return answer

 

4. 코드 상세 풀이

 

1. DFS 함수

def dfs(v, graph, visited):
    count = 1
    visited[v] = True
    
    for node in graph[v]:
        if not visited[node]: # 해당 노드 방문 이력이 없다면
            count += dfs(node, graph, visited) #카운드 증가하면서, 연결된 곳 찾아가기
    return count

 

현재 노드, 그래프, 방문 여부 배열을 인자로 받아서 몇 번 방문한 지 세어주는 DFS 함수를 만들어준다.

dfs를 선언하고, 다시 해당 노드와 연결된 노드(송전탑)들을 모두 방문해서 방문처리(True)를 하고 dfs를 재귀 형식으로 호출해 주면 된다.

 

2. solution 함수

1. 노드 리스트를 저장하는 그래프 생성 

    answer = 999999
    # 인접 리스트를 저장하는 그래프를 생성하자
    graph = [[] for _ in range(n+1)] # index에 node-1번 노드와 연결된 노드가 저장되어있음 # 첫 번호는 무시때리기 (0번은 없으므로)
    
    for a, b in wires: # 각 인덱스 노드에 ,연결된 노드 번호를 추가한다.
        graph[a].append(b) # 나자신은 b와 연결
        graph[b].append(a) # 연결된 b는 나와 연결
    
    print(graph)

- 우선 노드 개수 + 1만큼 빈 배열을 만들어준다.

- 그리고 wires 배열에서 현재 노드와 연결된 노드 번호를 추가해 준다.

** 참고로, 노드 번호와 인덱스 번호를 동일시하기 위해서 graph 배열을 n+1만큼 선언해 줬고, graph [0] 번째는 비어두도록 했다.

 

 

2. 반복문으로 간선을 한 개씩 끊어가면서 각각 송전탑 개수의 차이의 최소를 구한다.

    # 간선을 한개씩 끊어가면서 테스트해보자.
    for i in range(len(wires)): # 연결된 와이어 개수만큼 반복

 

 

2.1. 이때, visited 배열을 n+1개로 생성하여, 간선을 끊는 작업을 진행한다. 

        # 반복처리 배열 생성, 0번은 무조건 True이다.
        visited = [False] * (n+1)
        visited[0] = True 
    
        a,b = wires[i] # 끊을 간선을 저장 [1,3]
        
        # 간선 a-b를 끊는다
        graph[a].remove(b)
        graph[b].remove(a)

 

- visitied 배열의 첫 번째는 True로 설정하여 제외시켜 준다. (1~ n번까지 인덱싱 할 거라서)

- a, b에 서로 끊어낼 노드를 저장한다. [1,3]인 경우 1-3번을 끊어낼 것이다.

- remove() 함수로, 서로 연결된 노드를 삭제해서 a-b연결을 끊어낸다.

 

 

2.2 A와 B위치에서 각각 DFS로 송전탑의 개수를 구한다.

        # a에서 dfs를 시작한다. 
        #그러면 끊어진 b 통로 전까지 dfs로 개수를 셀 것이다.
        leftNodeCount = dfs(a, graph, visited)
        
        # b에서 dfs를 시작한다.
        # 그러면 b~ 끝까지 진행할것. (a와 연결된곳을 제외하고)
        rightNodeCount = dfs(b,graph,visited)

 

 

2.3. 두 개의 송전탑 개수의 차이(절댓값)를 구하고, answer과 비교해서 최소 값으로 결과를 갱신해 준다.

        # 두개의 송전탑 개수의 차이(절대값)을 구하고, 최소값으로 갱신해주자.
        answer = min(answer, abs(leftNodeCount - rightNodeCount))

** 참고로, answer는 처음에 99999로 선언해서 무조건 구한 값이 최소로 나오게 해 줬다.

 

 

2.4. 이제 끊은 간선을 다시 원래대로 연결해 준다. 그리고 결과를 리턴한다.

        # 끊어둔 간선을 다시 연결해주자.
        graph[a].append(b) # a->b 연결
        graph[b].append(a) # b->a 연결

    return answer

- 다시 처음 반복 지점으로 돌아가서 다음 송전탑 A, B를 끊어줘야 하기 때문이다.

 

---

4. 마무리

 

- 이 문제는 모르겠어서 처음에 다른 풀이를 보고, 그리고 답을 보면서 풀고, 다음날 다시 풀어보면서 풀이를 이해했다.

- DFS를 이용하기 위해 다시 graph 배열을 맞춤형으로 만들어줘야 하는 것을 스스로 생각하지 못했다.

- 이런 식으로 간선을 모두 끊는 게 완전탐색, 연결된 송전탑을 모두 방문해서 구하는 것이 DFS라는 것을 알게 됐다!

 

언젠가는 이런 문제도 혼자서 빠르게 풀 수 있으면 좋겠다.

 

---

읽어주셔서 감사합니다~

도움이 되셨다면 공감 부탁드립니다 😊