10159)저울

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

물체의 무게는 구체적으로 알 수 없지만 물체 끼리 비교해서 얻은 대소 관계는 알 수 있다.

주어진 예제에서 각 물체의 대소 관계는 아래와 같다.

1>2, 2>3, 3>4, 5>4, 6>5

각각의 물체를 비교한 결과를 이어 붙이면 아래처럼 정리할 수 있다.

1>2>3>4

6>5>4

1번 물체는 1,2,3,4와 대소 관계를 확인할 수 있지만 5,6과 대소 관계는 확인할 수 없다.

이 관계를 조금 더 쉽게 표현할 수 없을까 고민하다가 방향성 그래프와 유사한 면이 있음을 알게됬다.

4번 물체는 1,2,3번 물체와 5,6번 물체와 대소 관계를 알 수 있는데, 1,2,3번 물체는 5,6번 물체와 대소 관계를 알 수 없다.

여기서 1,2,3번은 4번으로 향하는 단방향 간선, 또 5,6번이 4번으로 향하는 단방향 간선이 있어서 4번은 다른 모든 물체와

비교 가능하지만, 4번에서 다른 물체로 향하는 단방향 간선이 없어서 1,2,3번과 5,6번 물체를 비교할 수 없다고 봤다.

방향 그래프로 각 물체간의 대소 관계를 표현한 그림이다.

a>b일때 a->b로 표현하였다.

각 물체간 대소 관계를 그래프로 표현하면 문제를  다루기 쉬워진다.

우선 1번에서 간선을 따라가며 2,3,4번을 방문하면 1번은 자신을 포함한 2,3,4와 비교 가능하고 5,6과는 비교 가능하지 않다.

2번에서 간선을 따라가면 1번과 비교 가능해야 하지만 2->1인 간선이 없어 의도와는 다른 결과가 나온다.

따라서 i번 노드에서 다른 노드를 방문했을 때 i번 노드에서 방문했다는 사실을 기록해야 한다.

#include<stdio.h>
#define TRUE 1
#define FALSE 0
 
void visitCompare(int **compare, int *isVisited, int N, int start) {
    if (isVisited[start]) return;
    isVisited[start] = TRUE;
 
    for (int j = 0; j < N;j++) {
        if (compare[start][j]) visitCompare(compare, isVisited, N, j);
    }
}
 
void initArray(int *A, int N) {
    for (int i = 0; i < N;i++) {
        A[i] = FALSE;
    }
}
 
int main() {
    int N, M;
    int **compare;
    int **isCompared;
    int *isVisited;
    int bigger, smaller;
    int count = 0;
 
    scanf("%d %d",&N,&M);
 
    compare = (int **)malloc(sizeof(int *)*N);
    for (int i = 0; i < N;i++) {
        compare[i] = (int *)calloc(N,sizeof(int));
    }
 
    isCompared = (int **)malloc(sizeof(int *)*N);
    for (int i = 0; i < N; i++) {
        isCompared[i] = (int *)calloc(N, sizeof(int));
    }
 
    isVisited = (int *)calloc(N, sizeof(int));
 
    for (int i = 0; i < M;i++) {
        scanf("%d %d",&bigger, &smaller);
        bigger--; smaller--;
        compare[bigger][smaller] = TRUE;
    }
 
    for (int i = 0; i < N;i++) {
        visitCompare(compare, isVisited, N, i);
 
        for (int j = 0; j < N;j++) {
            if (isVisited[j]) {
                isCompared[i][j] = TRUE;
                isCompared[j][i] = TRUE;
            }
        }
 
        initArray(isVisited, N);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!isCompared[i][j]) count++;
        }
        printf("%d\n", count);
        count = 0;
    }
 
    return 0;
}