문제

풀이

무작위 두 사람의 순위 관계가 주어지고, 전체 사람의 순위에 대한 질문을 묻는 문제.
플로이드 와샬로 해결할 수 있는 대표적인 문제이다.

플로이드 와샬 알고리즘은 3중 반복문을 통해
각각 x번 노드가 y번 노드를 거쳐서 z번 노드로 갈 수 있는지에 대한 것을 모두 체크해 준다.

위 원리를 이용해서 다음 식을 적용해주면 된다.

1. x번 사람이 y번 사람보다 순위가 높고 y번 사람의 z번 사람보다 순위가 높다면 x번 사람은 z번 사람보다 순위가 높다.
   (x>y && y>z => x>z)

2. x번 사람이 y번 사람보다 순위가 낮고 y번 사람의 z번 사람보다 순위가 낮다면 x번 사람은 z번 사람보다 순위가 낮다.
   (x<y && y<z => x<z)

플로이드 와샬의 자주 쓰이는 형태 중 하나이다.

코드

#include <string>
#include <vector>
#include <algorithm>
#define INF 2147483647
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    vector<vector<int>> floyd(n, vector<int>(n, 0));
    for (int i = 0; i < results.size(); i++) {
        int x = results[i][0];
        int y = results[i][1];
        x--;
        y--;
        floyd[x][y] = 1;
        floyd[y][x] = -1;
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (floyd[i][k]==1 && floyd[k][j]==1 ) {
                    floyd[i][j] = 1;
                }
                else if (floyd[i][k]==-1 && floyd[k][j]==-1) {
                    floyd[i][j] = -1;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (count(floyd[i].begin(), floyd[i].end(), 0) == 1) answer++;
    }

    return answer;
}

후기

백준에도 비슷한 유형의 문제가 있다.
1613 역사 https://www.acmicpc.net/problem/1613
2458 키순서 https://www.acmicpc.net/problem/2458