[Programmers] Lv2 - 전력망을 둘로 나누기

문제

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

프로그래머스

 

풀이

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.
wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
1 ≤ v1 < v2 ≤ n 입니다.전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

 

해당 문제는 DFS(깊이우선탐색), 그래프를 사용하는 문제다.

 

나는 아직 자료구조적인 문제엔 약해서, 답을 보고 공부하는 방식을 택했다^^;

아래는 AI를 통해 얻어낸 정답 코드다.

def create_graph(n, wires):
    """
    전선 정보를 바탕으로 그래프를 생성하는 함수

    n: 송전탑의 개수
    wires: 전선 정보를 담은 2차원 리스트, 각 전선 정보는 [v1, v2] 형태로 주어지며 v1과 v2는 연결된 두 송전탑의 번호를 나타냄

    그래프는 무방향 그래프로 표현되며 인접 리스트를 사용하여 생성
    송전탑의 번호는 1부터 시작하므로 인덱스 0은 사용하지 않음
    """
    graph = [[] for _ in range(n + 1)]
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
    return graph

def dfs(graph, start, visited):
    """
    DFS 탐색을 수행하여 연결된 송전탑의 개수를 세는 함수

    graph: 그래프 정보를 담은 2차원 리스트
    start: 탐색을 시작할 송전탑의 번호
    visited: 송전탑의 방문 여부를 나타내는 리스트, visited[i]는 i번 송전탑의 방문 여부를 나타내며 초기값은 모두 False로 설정됨

    DFS 탐색을 사용하여 연결된 송전탑 탐색
    스택을 사용하여 DFS 구현
    방문한 송전탑의 개수를 count 변수에 저장하여 반환
    """
    stack = [start]
    count = 0
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            count += 1
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.append(neighbor)
    return count

def solution(n, wires):
    """
    전력망을 최적으로 분할하여 두 네트워크의 송전탑 개수 차이의 최솟값을 구하는 함수

    n: 송전탑의 개수
    wires: 전선 정보를 담은 2차원 리스트

    하나의 전선을 끊어서 두 개의 네트워크로 분할
    각 네트워크의 송전탑 개수 차이를 최소화하는 것이 목표
    모든 전선에 대해 하나씩 제거해보면서 송전탑 개수 차이 계산
    최솟값을 찾아 반환

    문제 해결에 필요한 개념: 그래프 이론, 트리 구조, DFS 탐색, 브루트포스 알고리즘
    """
    answer = float("inf")

    for i in range(len(wires)):
        # 그래프 생성
        graph = create_graph(n, wires[:i] + wires[i + 1 :])

        # 첫 번째 송전탑에서 시작해서 탐색
        visited = [False] * (n + 1)
        count = dfs(graph, 1, visited)

        # 두 네트워크의 송전탑 개수 차이 계산
        diff = abs(count - (n - count))
        answer = min(answer, diff)

    return answer

 

문제의 요구사항은 1) 최대한 두 전력망의 네트워크 수가 비슷, 2) 두 전력망의 차이값을 절댓값으로 반환.

즉 두 전력망의 차이값이 가장 적은경우가 답이 되겠다.

 

1. 먼저 answer을 무한대("inf")로 선언해준다.
2. 송전탑 리스트 wires의 길이만큼 순회한다. 여기서 i는 제거할 전선이다.
3. i를 제외한 wires를 create_graph 함수를 통해 그래프로 만들어준다.
4. 그 다음 송전탑의 갯수(n)만큼 visited = [False]를 선언한다.
   => 여기서 [False] * n 이 아닌 [False] * (n+1)로 선언한 이유는 인덱싱을 편리하게 하기 위해서다. 송전탑의 번호는 1부터 시작하기 때문.
5. 해당 그래프와 visited로 dfs함수를 실행한다.
   dfs 코드 실행 예시는 아래와 같다.
   

   graph = [[], [2, 3], [1, 3], [1, 2, 4], [3, 5, 6], [4], [4]]
   start = 1
   visited = [False] * (len(graph))

   만약 위와 같은 graph, start, visited 데이터가 주어졌다고 가정해보자.
   
   아래는 AI를 통해 작성한 dfs 함수 실행 과정이다.
   dfs 함수 실행 과정:

   1. stack을 [start]로 초기화하고, count를 0으로 초기화합니다.
      • stack = [1], count = 0
   2. stack이 비어있지 않은 동안 다음 과정을 반복합니다.
      • node를 stack에서 pop합니다. node = 1
      • visited[node]가 False인 경우:
        • visited[node]를 True로 설정합니다. visited[1] = True
        • count를 1 증가시킵니다. count = 1
        • graph[node]에 연결된 송전탑들을 확인합니다. graph[1] = [2, 3]
          • 연결된 송전탑 2가 visited[2] = False이므로 stack에 추가합니다. stack = [3, 2]
          • 연결된 송전탑 3이 visited[3] = False이므로 stack에 추가합니다. stack = [3, 2]
   3. stack에서 다음 노드를 pop합니다. node = 2
      • visited[2] = False이므로 visited[2]를 True로 설정합니다.
      • count를 1 증가시킵니다. count = 2
      • graph[2] = [1, 3]에 연결된 송전탑들을 확인합니다.
        • 연결된 송전탑 1은 이미 visited[1] = True이므로 stack에 추가하지 않습니다.
        • 연결된 송전탑 3은 이미 stack에 있으므로 추가하지 않습니다.
   4. stack에서 다음 노드를 pop합니다. node = 3
      • visited[3] = False이므로 visited[3]를 True로 설정합니다.
      • count를 1 증가시킵니다. count = 3
      • graph[3] = [1, 2, 4]에 연결된 송전탑들을 확인합니다.
        • 연결된 송전탑 1과 2는 이미 visited가 True이므로 stack에 추가하지 않습니다.
        • 연결된 송전탑 4는 visited[4] = False이므로 stack에 추가합니다. stack = [4]
   5. stack에서 다음 노드를 pop합니다. node = 4
      • visited[4] = False이므로 visited[4]를 True로 설정합니다.
      • count를 1 증가시킵니다. count = 4
      • graph[4] = [3, 5, 6]에 연결된 송전탑들을 확인합니다.
        • 연결된 송전탑 3은 이미 visited[3] = True이므로 stack에 추가하지 않습니다.
        • 연결된 송전탑 5와 6은 visited[5] = False, visited[6] = False이므로 stack에 추가합니다. stack = [6, 5]
   6. stack에서 다음 노드를 pop합니다. node = 5
      • visited[5] = False이므로 visited[5]를 True로 설정합니다.
      • count를 1 증가시킵니다. count = 5
      • graph[5] = [4]에 연결된 송전탑들을 확인합니다.
        • 연결된 송전탑 4는 이미 visited[4] = True이므로 stack에 추가하지 않습니다.
   7. stack에서 다음 노드를 pop합니다. node = 6
      • visited[6] = False이므로 visited[6]를 True로 설정합니다.
      • count를 1 증가시킵니다. count = 6
      • graph[6] = [4]에 연결된 송전탑들을 확인합니다.
        • 연결된 송전탑 4는 이미 visited[4] = True이므로 stack에 추가하지 않습니다.
   8. stack이 비어있으므로 반복을 종료하고, count 값인 6을 반환합니다.

   이렇게 dfs 함수는 시작 노드부터 연결된 송전탑들을 깊이 우선 탐색하면서 방문한 송전탑의 개수를 세어 반환합니다. 위의 예시에서는 1번 송전탑부터 시작하여 연결된 모든 송전탑을 방문했으므로 count 값은 6이 됩니다.
6. dfs 실행 결과값 count를 이용해 두 전력망의 차이를 계산한다.
7. 마지막으로 min()함수를 통해 그 전의 차이값과 현재 차이값 중 더 적은 값을 answer로 재할당한다.

 

풀이는 이것으로 끝이다.

나는 이제 자료구조 공부를 하러 가야겠다... 프로그래머스도 잠시 중단하고 백준으로 옮겨갈생각이다.

유형별로 풀어보기엔 백준이 더 나은듯하다. 문제의 양도 훨씬 많고~