[Graph] 전력망을 둘로 자르기 (프로그래머스 강의)

문제

https://school.programmers.co.kr/learn/courses/14760/lessons/125501

• n : 전체 송전탑 개수 (정수형)

• wires : 전선 정보 (이차원 배열)

• 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개의 영역으로 분할하려고 한다.

• 양쪽 영역의 송전탑 개수를 최대한 비슷하게 두 그룹으로 나눴을 때, 두 전력망이 가지고 있는 송전탑의 개수 차이의 최솟값을 리턴하는 함수를 작성해라.

입출력 예제

예제 1)

예제 2)

예제 3)

풀이

• 본 문제는 <프로그래머스와 함께하는 PCCP합격 대비 : 실전 모의고사 해설 강의(Python편)>을 수강 후, 코드를 작성하였다.

• 본 문제를 소스 코드로 구현하면서 새롭게 알게 된 점은 두 가지가 있다.

  1) 전역변수 사용하는 방법 (global 선언하기)
  2) 이차원 배열에서 두 개 이상의 값을 반복문을 통해 불러오는 방법

for a, b in graph:
	# a, b를 사용한 내용 작성

트리(tree) vs 그래프(graph)

• 트리는 회로가 존재하지 않는다.
• 그래프는 회로가 존재할 수 있다.

인접 리스트 vs 인접 행렬

추후 보완 예정

코드

정답

• 인접 리스트(그래프) 사용
• DFS 사용
• 전역 변수 및 반복문에서 이차원 배열의 값 두 개 이상을 한번에 가져오도록 코드를 작성함

# 정답 결과 출력 코드

# 새로 알게된 점
# 1) 전역변수 사용 방법
# 2) 이차원 배열에서 두 개 이상의 값을 반복문을 통해 불러오는 방법

cnt = 0
def DFS(v1, check, graph):
    global cnt      # cnt를 전역변수로 선언함
    check[v1] = 1       # 현재 노드를 방문했다고 체크 (해당 문제는 존재하는 전력망의 개수를 세는 것이므로, 첫 노드부터 개수를 셈)
    cnt += 1
    for i in graph[v1]:
        if check[i] == 0:       # 연결된 노드들 중 방문하지 않은 노드들을 계속 탐색
            DFS(i, check, graph)
            

def solution(n, wires):
    global cnt      # cnt 함수를 전역변수로 선언
    answer = 100    # 최솟값을 찾는 것이므로, 최대 값을 초기 answer의 값으로 초기화함
    
    graph = [[] for _ in range(n+1)]        # 연결된 간선 정보를 저장할 그래프 생성 (1~9번 배열에 각각 연결된 노드 정보를 저장할 것임)
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)        # 만약 그래프가 단방향 그래프이면, 이 줄의 코드는 생략
        
    for v1, v2 in wires:        # 연결된 간선들을 차례로 하나씩 끊어가면서 양쪽 노드의 개수 차를 비교함
        check = [0]*(n+1)
        check[v2] = 1       # 끊을 노드의 (a, b) 중 b 노드의 check 여부를 참으로 바꿈 (이미 방문한 노드라 가정하고 다시 못하도록 함)
        cnt = 0         # 한 영역에 연결된 노드의 개수
        DFS(v1, check, graph)       # 끊을 노드 (a,b)의 a 값과 방문여부 체크 배열, 그래프 배열을 DFS에 넘겨줌
        # 한 쪽의 송전탑의 개수 : cnt개, 다른 쪽의 송전탑의 개수 : n-cnt
        # answer : 현재까지 양 쪽 송전탑 개수 차의 최솟값
        answer = min(answer, abs(cnt-(n-cnt)))
        
    return answer

실행 결과 출력

💡 오류 발생 (수정 중)

• cnt 변수를 전역변수로 선언하지 않고 DFS에서 최종 cnt를 solution 함수로 리턴받아 사용함
• 이때 제대로 된 정답이 출력되지 않는데, 그 이유 찾아내보자 🧐

def DFS(v1, cnt, check, graph):
    check[v1] = 1       # 현재 노드를 방문했다고 체크
    cnt += 1
    for i in graph[v1]:
        if check[i] == 0:       # 연결된 노드들 중 방문하지 않은 노드들을 계속 탐색
            DFS(i, cnt, check, graph)
    return cnt
            

def solution(n, wires):
    answer = 100    # 최솟값을 찾는 것이므로, 최대 값을 초기 answer의 값으로 초기화함
    
    graph = [[] for _ in range(n+1)]        # 연결된 간선 정보를 저장할 그래프 생성 (1~9번 배열에 각각 연결된 노드 정보를 저장할 것임)
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)        # 만약 그래프가 단방향 그래프이면, 이 줄의 코드는 생략
        
    for v1, v2 in wires:        # 연결된 간선들을 차례로 하나씩 끊어가면서 양쪽 노드의 개수 차를 비교함
        check = [0]*(n+1)
        check[v2] = 1       # 끊을 노드의 (a, b) 중 b 노드의 check 여부를 참으로 바꿈 (이미 방문한 노드라 가정하고 다시 못하도록 함)
        cnt = 0         # 한 영역에 연결된 노드의 개수
        cnt_v1 = DFS(v1, cnt, check, graph)       # 끊을 노드 (a,b)의 a 값과 방문여부 체크 배열, 그래프 배열을 DFS에 넘겨줌
        # 한 쪽의 송전탑의 개수 : cnt개, 다른 쪽의 송전탑의 개수 : n-cnt
        # answer : 현재까지 양 쪽 송전탑 개수 차의 최솟값
        answer = min(answer, abs(cnt_v1-(n-cnt_v1)))
        
    return answer