[백준] 1412번 일방통행

[적용한 알고리즘]

그래프, 플로이드

 

[아이디어]

1. 단방향, 양방향 간선이 섞인 그래프를 DAG 로 바꿀 수 있느냐? 가 문제다.

2. 결국 주어진 그래프에서 사이클이 없도록 그래프를 구성할 수 있느냐? 가 핵심이다.

3. 가능한 그래프의 종류를 국소적으로 살펴보면서 생각해보면,

 1) 단방향 간선으로 이루어진 사이클이 존재하는 경우 : 무조건 NO

 2) 양방향 간선으로 이루어진 사이클이 존재하는 경우 : 사이클은 무조건 DAG 로 바꿀 수 있음 (위상정렬)

 3) 단/양 섞인 사이클 : 이것 역시 가능

 4) 사이클이 없는 단방향 그래프 : 설명할 필요 없이 가능

 

따라서 곰곰이 생각하다보면 1) 만 걸러주면 되므로,

단방향 사이클이 존재하는지만 생각해보면 된다. 

 

[교훈]

문제 한참 어렵다가 아이디어 하나로 모든게 술술 풀릴 때 쾌감이란

블로그 업데이트를 한참 못했으니 밀린 것도 좀 업데이트 해야겠다.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N = 101;
bool Dist[MAX_N][MAX_N];
char Path[MAX_N][MAX_N];

int main(){
    int N;
    scanf("%d", &N);

    for (int i = 1; i <= N; i++){
        scanf("%s", Path[i] + 1);
    }

    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
           Dist[i][j] = (Path[i][j] == 'Y' && Path[j][i] == 'N');
        }
    }

    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (Dist[i][k] && Dist[k][j]){
                    Dist[i][j] = true;
                }
            }
        }
    }

    for (int i = 1; i <= N; i++){
        if (Dist[i][i]){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}