99클럽 코테 스터디 1일차 TIL - 완전 탐색

📎 문제링크

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

🤔 문제 이해 및 알고리즘 유형

알고리즘 유형

- 완전 탐색

💡 문제 해결 방법

💻 코드

def solution(n, wires):
    answer = 100
    test = [[wires[i] for i in range(len(wires)) if i != j] for j in range(len(wires))] # 전선 하나씩 끊어보기
    
    for wire in test:
        graph = [[] for _ in range(n)] # 인접 리스트 생성
        visited = [False] * n
        for w in wire:
            graph[w[0]-1].append(w[1]-1) # 노드 양방향으로
            graph[w[1]-1].append(w[0]-1) # 연결 추가
        m = dfs(graph, visited, 0, 1) # 연결된 송전탑 수
        answer = min(answer, abs(n-2*m)) # 일부m과 (전체n - 일부m)으로 나눠짐. |(n-m) - m| = |n - 2*m|
    return answer

def dfs(graph, visited, start, n):
    visited[start] = True # 방문 처리
    for i in graph[start]:
        if not visited[i]:
            n = dfs(graph, visited, i, n+1) # n증가
    return n

✔ 생각해봐야 할 점

 

전선을 끊어서 완전 탐색을 해야 한다는 것까지는 생각했지만 이후 과정을 생각하지 못했다.

과정을 정리해 보자면

1) 전선 하나씩 끊어보기

각 전선을 하나씩 끊어보고, 끊어진 전선으로 인해 두 개의 서브 그래프가 형성한다.

 

2) 그래프 탐색 (DFS)

끊어진 두 개의 서브 그래프를 탐색한다.

 

3) 최소 차이를 계산한다.