[BOJ알고리즘, C++]#10159_저울, 최단 경로, 길 찾기, 플로이드-워셜

 

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 플로이드-워셜

https://webddevys.tistory.com/298

[알고리즘]#2_길 찾기 알고리즘

플로이드-워셜 알고리즘은 '음수 가중치'를 포함하는 가중치 그래프의 "전체-쌍 최단 경로"를 구하는 알고리즘입니다. 특히, 경유 정점(간접적으로 연결된 서로 다른 정점) 개념이 강조되는 문제에서 플로이드-워셜 알고리즘이 유용합니다. 일반적으로, 플로이드-워셜 알고리즘은 총 3개의 for문을 통해 시작 정점과 도착 정점의 최단 경로 값이 경유 정점을 가질 경우 최단 경로 값의 업데이트 여부를 결정하고, 이를 통해 그래프의 전체-쌍 최단 경로 값을 구합니다.

 

2. 플로이드-워셜을 통해 직/간접적으로 연결된 정점 쌍 구하기!

1. 먼저, 주어진 두 정점의 연결 정보를 저장합니다.
2. 플로이드-워셜 알고리즘을 통해 어느 두 정점이 간접적으로 연결되어 있는지 확인합니다.
3. 마지막으로, 출발 정점과 도착 정점을 순회하며 서로 직/간접적으로 연결되어 있지 않은 두 정점 쌍을 찾아 카운트합니다.

 

---

 

#3. 코드

/*
    @문제 : N개의 물건에 대한 무게 정보가 '비교'연산으로 주어졌을 때, 각 물건의 비교 결과를 직/간접적으로 알 수 없는 물건의 개수
    @설명
        1. 플로이드-워셜 : "출발점 -> 경유점 -> 도착점"을 통해 '전체-쌍 최단 경로'를 파악할 수 있는 알고리즘
        2. 
*/

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 101

int N, M;
bool graph[MAX][MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> M;

    while(M--)
    {
        int more, less;
        cin >> more >> less;

        graph[more][less] = true;
    }

    // 플로이드-워셜 : 3단 for-loop, u 와 k, 그리고 k와 v의 관계를 통해 u와 v의 관계를 '간접적'으로 알 수 있다.
    for(int k=1; k<=N; ++k)
    {
        for(int u=1; u<=N; ++u)
        {
            for(int v=1; v<=N; ++v)
            {
                if(graph[u][k] && graph[k][v])
                    graph[u][v] = true;
            }
        }
    }

    // 각 물건 마다 직/간접적으로 비교 관계를 알 수 없는 물건을 센다
    for(int i=1; i<=N; ++i)
    {
        int ans = 0;
        for(int j=1; j<=N; ++j)
        {
            if(i!=j && !graph[i][j] && !graph[j][i])
                ans++;
        }
        cout << ans << '\n';
    }

    return 0;
}

 

---