일방통행

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

"""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()

• Dependency: teflib.graph.is_acyclic