[python] 백준 11562 백양로 브레이크

https://www.acmicpc.net/problem/11562

11562번: 백양로 브레이크

 

 

문제 해결

• graph[u][v] : u에서 v까지 가는데 필요한 양방향화 필요한 길 개수
• 처음에 INF로 정의한다음 연결되어있다고 입력값이 주어지만 graph[u][v] = 0
• 만약 양방향이 아니고 u→v는 연결이 되어있는데 v→u는 연결이 안되어있으면 graph[v][u] = 1로 정의
• 플로이드-위셜을 이용하여 필요한 양방향화 길의 개수를 구할 수 있다.
• 플로이드-위셜로 최소거리가 아닌 필요한 양방향화 길의 갯수 등도 구할 수 있다는 유형을 처음 접해보았다.

 

 

CODE

 

import sys
input = sys.stdin.readline
INF = int(sys.maxsize)

def Floyd():

    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if graph[i][j] > graph[i][k] + graph[k][j]: # 어떻게 해서라도 i에서 j로 못가는 경우 최소 양방이 필요한 개수
                    graph[i][j] = graph[i][k] + graph[k][j]

    for i in range(n+1):
        graph[i][i] = 0

if __name__ == "__main__":
    n, m = map(int, input().split())
    graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

    for _ in range(m):
        u, v, b = map(int, input().split())
        if b==0:
            graph[u][v] = 0
            graph[v][u] = 1
        else:
            graph[u][v] = 0
            graph[v][u] = 0

    Floyd()

    for _ in range(int(input())):
        s, e = map(int, input().split())
        print(graph[s][e])