일방통행 도로 만들기
면접 대비시간 제한2초메모리 제한128 MB
N개의 도시를 잇는 양방향 도로를 모두 일방통행으로 바꿔서 전체 도로망에 방향 순환이 생기지 않게 할 수 있는지 판별합니다.
문제
다솜제국에는 N개의 도시가 있다. 두 도시 사이의 도로는 한쪽 방향으로만 갈 수 있는 일방통행 도로일 수도 있고, 양쪽 방향으로 모두 갈 수 있는 양방통행 도로일 수도 있다.
왕 이다솜은 모든 양방통행 도로를 하나의 방향만 가진 일방통행 도로로 바꾸려고 한다. 각 양방통행 도로마다 두 방향 중 하나를 선택할 수 있다.
변경이 끝난 뒤에는 어떤 도시 x에서도 출발하여 도로를 따라 이동한 후 다시 x로 돌아오는 경로가 없어야 한다. 주어진 도로 정보에 대해 이런 변경이 가능한지 판별하라.
입력
첫째 줄에 도시의 개수 N (2 <= N <= 50)이 주어진다.
다음 N개의 줄에는 도로 정보를 나타내는 N글자 문자열이 주어진다. i번째 줄의 j번째 문자는 Y 또는 N이다. Y이면 i번 도시에서 j번 도시로 가는 도로가 있고, N이면 없다는 뜻이다. i번째 줄의 i번째 문자는 항상 N이다.
출력
가능하면 YES, 불가능하면 NO를 출력한다.