그래프

1. 노드, 간선에 대한 정보가 주어질 때, 트리(graph) 형식으로 구성하는 예제 + DFS

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

def solution(n, wires):
    def dfs(graph, start, visited):
        count = 1
        visited[start] = True
        for i in graph[start]:
            if not visited[i]:
                count += dfs(graph, i, visited)
        return count
        
    # 그래프를 구성하는 방법!
    graph = [[] for _ in range(n+1)] # n+1인 이유는, 노드 번호와 인덱스의 번호를 맞추기 위해서
    for v1, v2 in wires: # graph의 각 요소는, 각 노드와 연결된 노드들의 정보를 담은 리스트
        graph[v1].append(v2)
        graph[v2].append(v1)
    print(graph)
    answer = n
    # 전선을 끊는 완전 탐색
    for v1, v2 in wires:
        # 전선 끊기
        graph[v1].remove(v2)
        graph[v2].remove(v1)
        
        # dfs 방식으로 한 쪽 전력망의 노드 개수 파악
        visited = [False] * (n+1)
        count = dfs(graph, v1, visited)
        
        answer = min(answer, abs(count - (n-count)))
        
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    return answer

 

 

2. 플로이드-워셜 알고리즘

- 모든 쌍 간의 관계를 파악하는 알고리즘

- 삼중 for 문에서 k,j,i 를 기반으로 로직을 짤 때 순서에 주의하기

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

def solution(n, results):
    # results를 기반으로, 직접적인 승패 관계를 그래프로 구성
    win_graph = [ [False] * (n+1) for _ in range(n+1) ]
    lose_graph = [ [False] * (n+1) for _ in range(n+1) ]
    for winner, loser in results:
        win_graph[winner][loser] = True
        lose_graph[loser][winner] = True
    
    # 플로이드 워셜 알고리즘으로, 모든 선수 간의 간접적인 승패 파악하기
    for k in range(1, n+1):  # 중간 노드 선수
        for j in range(1, n+1): # 시작 노드
            for i in range(1, n+1): # 목표 노드
                if win_graph[j][k] == True and win_graph[k][i] == True:
                    win_graph[j][i] = True
                if lose_graph[j][k] == True and lose_graph[k][i] == True:
                    lose_graph[j][i] = True
    
    answer=0
    # 선수의 승패 관계를 기반으로 확실한 순위를 매길 수 있는 선수 파악하기
    for player in range(1, n+1):
        count = 0
        for counter in range(1, n+1):
            if win_graph[player][counter] == True or lose_graph[player][counter] == True:
                count += 1
        
        if count == (n-1):
            answer += 1
    
            
    return answer