[백준] No.10159 - 저울 (C++, 플로이드-와샬)

문제

 

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

10159번: 저울

 

풀이

 

solved.ac 난이도: Gold 3

 

모든 두 정점 쌍 사이의 거리를 구하는 플로이드-와샬(Floyd-Warshall) 최단 경로 알고리즘을 조금 변형해서 푸는 문제.

플로이드 알고리즘은 두 정점의 최단 거리를 구하지만 만약 두 정점 사이의 경로가 없다면 dist의 초기화 값이 INF값이 그대로 남게 된다.

즉, adj[i][j]의 초기화 값이 그대로 남았다면 두 정점은 서로 도달할 수 없다는 것을 알 수 있다.

 

adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

adj[i][j]는 i에서 j 정점까지의 최단 거리를 저장한다.

 

 

만약 두 정점이 연결되어 있는지만 확인하고 싶다면 최단 거리를 구하는 점화식을 다음과 같이 변형하면 된다.

is_adj[i][j] = is_adj[i][j] || (is_adj[i][k] && is_adj[k][j]);

is_adj[i][j]는 i와 j정점이 연결되는지의 여부만 bool형으로 저장한다.

 

void Floyd(){
  for(int k=1; k<=object_num ; ++k)
    for(int i=1; i<=object_num ; ++i)
      for(int j=1; j<=object_num ; ++j)
        is_adj[i][j] = is_adj[i][j] || (is_adj[i][k] && is_adj[k][j]);
}

 

 

플로이드를 수정했다면 정점들을 연결하는 간선은 측정된 물건의 정보로 동일한 단방향 간선을 만들어 주면된다.

예를 들어 가벼운 물건이 무거운 물건으로 진입 간선을 이어준다면 예제의 그래프는 다음과 같이 생성된다.

 

 

서로 비교를 통해 결과를 알 수 있는 1과 4번 물건은

1번에서 4번으로 이동할 수는 없지만 4번에서 1번으로 이동할 수는 있으므로 두 물건은 비교가 가능하다.

 

하지만 비교할 수 없는 2번과 5번 물건은 서로의 정점으로 이동할 수 없으므로 비교가 불가능하다.

간선의 방향은 반대로 무거운 물건에서 가벼운 물건으로 이어주어도 동일한 결과를 낸다.

 

 

코드