테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 일방통행 ======

===== 풀이 =====
  * 일방통행인 길들 사이에서 사이클이 생기지만 않는다면, 양방통행인 길에서는 언제나 사이클이 생기지 않는 방향으로 길을 제거할수 있다.
  * 결국 문제는 양방통행인 길들을 제외한 상태에서, 일방통행인 길들로만 이루어진 사이클이 있는지를 확인하는 것으로 해결 가능하다.
  * 일반통행인 길들만으로 그래프를 만들고 위상정렬을 통해서 DAG 여부를 확인해주면 된다. 시간복잡도는 O(|E|)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1412. 일방통행".

- Problem link: https://www.acmicpc.net/problem/1412
- Solution link: http://www.teferi.net/ps/problems/boj/1412

Tags: [graph]
"""

from teflib import graph as tgraph


def main():
    N = int(input())
    mat = [input() for _ in range(N)]

    graph = [[] for _ in range(N)]
    for r, row in enumerate(mat):
        for c, x in enumerate(row):
            if x == 'Y' and mat[c][r] == 'N':
                graph[r].append(c)

    print('YES' if tgraph.is_acyclic(graph) else 'NO')


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:graph#is_acyclic|teflib.graph.is_acyclic]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}