파이썬 알고리즘 312번 | [백준 11562번] 백양로 브레이크 - 플로이드 워셜 (3중 for문)

312. 백양로 브레이크

1) 어떤 전략(알고리즘)으로 해결?

• 플로이드 워셜

<코딩 설명 (주석) & 내 풀이>

import sys
n,m = map(int, sys.stdin.readline().rstrip().split())
graph = list([int(1e9) for _ in range(n+1)] for _ in range(n+1))

for i in range(m) : 
    u,v,b = map(int, sys.stdin.readline().rstrip().split())
    # b가 0일 경우 u에서 v로 가는 일방통행
    # b가 1일 경우 u와 v를 잇는 양방향 길이다.  
    # 바꾸는 데 드는 비용 
    cost_1 = 1
    cost_0 = 0 
    # u->v는 항상 경로가 존재 
    graph[u][v] = cost_0 
    if b==1 : # 양방향
        graph[v][u] = cost_0
    else :  # 일방통행
        graph[v][u] = cost_1 # 변경 비용 소요 됨 

for k in range(1,n+1) : 
    for i in range(1,n+1) : 
        for j in range(1,n+1) :
            if(i==j) : 
                graph[i][j] = 0 
                graph[j][i] = 0 
            else : 
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

k = int(sys.stdin.readline().rstrip())
for i in range(k) : 
    s,e = map(int, sys.stdin.readline().rstrip().split())
    # 각 질문에 대해, 최소 몇 개의 일방통행인 길을 
    # 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력한다.
    print(graph[s][e])

< 내가 틀린 풀이>

• 10 프로에서 틀린 풀이

import sys
n,m = map(int, sys.stdin.readline().rstrip().split())
graph = list([int(1e9) for _ in range(n+1)] for _ in range(n+1))

for i in range(m) : 
    u,v,b = map(int, sys.stdin.readline().rstrip().split())
    # b가 0일 경우 u에서 v로 가는 일방통행
    # b가 1일 경우 u와 v를 잇는 양방향 길이다.  
    # 바꾸는 데 드는 비용 
    cost_1 = 1
    cost_0 = 0 
    # u->v는 항상 경로가 존재 
    graph[u][v] = cost_0 
    if b==1 : # 양방향
        graph[v][u] = cost_0
    else :  # 일방통행
        graph[u][v] = cost_1 # 변경 비용 소요 됨 

for k in range(1,n+1) : 
    for i in range(1,n+1) : 
        for j in range(1,n+1) :
            if(i==j) : 
                graph[i][j] = 0 
            else : 
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

k = int(sys.stdin.readline().rstrip())
for i in range(k) : 
    s,e = map(int, sys.stdin.readline().rstrip().split())
    # 각 질문에 대해, 최소 몇 개의 일방통행인 길을 
    # 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력한다.
    print(graph[s][e])

• 아래 부분에서 틀렸었다.

    graph[u][v] = cost_0 
    if b==1 : # 양방향
        graph[v][u] = cost_0
    else :  # 일방통행
        graph[u][v] = cost_1 # 변경 비용 소요 됨 

graph[u][v] = cost_0 는 항상 비용이 0이고 graph[v][u] 만 달라진다.

<배운 점>

• 플로이드 워셜의 응용, 비용을 역으로 생각해서 기록한다는 접근법이 독특했다.