[백준/Python]11562: 백양로 브레이크

문제

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

백준 문제집 - 0x1C강 - 플로이드 알고리즘

알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜

---

풀이

 

일반적인 최단경로 문제와는 다르게 비용이 아닌 "일방통행"이냐, "양방향"이냐의 정보만 주어진다. 요 점이 포인트다.
그리고 "모든 길을 양방향으로 바꿨을경우 이동 불가능한 경로는 없다"라고 되어있는데, 아예 이동 불가능한 길은 양방향으로 바꿀 수 없다.
a → b든 b → a든 이미 일반통행이 존재했던 경우에만 양방향으로 바꿀 수 있다.

 

그렇다면 일반통행, 양방향, 막힌 길을 별도로 표시해줘야한다.

1. 양방향 길(b=1): 추가 비용 없이 양쪽 모두 이동 가능하므로 0
2. 일반통행 길(b=0)
   • 정방향: 추가 비용 0
   • 역방향: 추가 비용 1(양방향으로 바꿔야 함)
3. 막힌 길: 이동 불가능(INF)

 

분류해서 저장 후 플로이드 워셜을 수행하면 a → b 이동 시 몇개의 길을 양방향으로 바꿔야하는지 구할 수 있다.
만약 a → b 사이에 공사 or 막힌 길이 없다면 0, 공사가 필요한 경우 역방향은 1로 저장해뒀으니 그래프의 값이 곧 공사 횟수인셈이다.

 

전체 코드

# 메모리: 32412KB / 시간: 1152ms
from sys import stdin


input = stdin.readline
INF = int(1e9)

def main():
    # 건설되어 있는 도로(양방향, 일반도로 u -> v)라면 0으로 설정.
    # 일반 도로에서 역방향, v -> u의 값은 1로 설정한다.
    # => 건설되지 않은 역방향 도로 v -> u가 최단거리에 포함되는 갯수 = 양방향 도로로 변경해야하는 도로의 갯수
    N, M = map(int, input().split())
    graph = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

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

        if b == 1:
            graph[v-1][u-1] = 0
        else:
            graph[v-1][u-1] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

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


main()

 

사실 어떻게 풀었는지 까먹었는데, 다시 풀다보니 기억났다... 글쓰기의 순기능이다.
예전에 풀었던 문제들도 이따금씩 다시 풀어봐야겠다.