백준 1412 자바 - 일방통행 (BOJ 1412 JAVA)

문제 : https://www.acmicpc.net/problem/1412

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01400/BOJ_1412.java

 

 

  플래 중위권 문제치곤 그리 어렵지 않았다. 구현이 어렵다기보다는 아이디어를 떠올리기 좀 어려울 수 있는 문제라 티어가 높게 책정된 듯 하다.

 

  일단 '도시 x에서 출발해서 다시 그 도시 x로 돌아올 수 없게 만드는 것이다.' 부분을 만족하려면, 결국 자기 자신으로 되돌아오는 Cycle이 없으면 된다. 여기까진 쉽게 생각할 수 있는데 그럼 양방통행와 일방통행 도로의 두 종류가 있는 상황에서 어떻게 해야 Cycle을 없앨 수 있는지가 관건이다.

 

  그래서 일단 그려보며 열심히 생각해봤는데, 암만봐도 뭔짓을 해도 양방통행 도로는 Cycle에 영향을 끼칠수가 없다! 어떻게든 Cycle을 제거하는 방향으로 선택할 수 있다는 의미이다. 그래서 양방통행 도로는 아예 생각하지 않고 건드릴 수 없는 일방통행 도로만 생각해보기로 했다. 즉, 양방통행 도로는 Cycle에 영향을 끼칠 수 없으니 걷어내고 건드릴 수 없는 일방통행 도로만 확인해서 거기서 Cycle이 있다면 답은 'NO'가 된다.

 

  그럼 로직은 아래와 같이 짤 수 있다.

1. 입력받은 간선 정보 중 양방통행 도로는 제거한다. (코드의 receiveInput() 이후 removeDoublyEdge())

2. 남은 일방통행 도로에서 도시 x에서 도시 x로의 Cycle이 생기는지 확인한다.

 

간단히 위 과정으로 끝이다.

 

... 실은 좀 많이 틀렸다.

  싸이클 판정 부분에 대한 이해가 명확하지 않았기 때문인데, union-find로 자꾸 싸이클 찾으려고 하니 당연히 틀릴 수 밖에 없었다 ㅠ 로직은 맞는 것 같아 혹시나 해서 dfs로 싸이클 판정 해보니 맞았다. 찾아보니 union-find로 싸이클 찾는건 무방향 그래프에서 쓰는거라고 한다. 그동안 문제풀면서 싸이클 판정 하는걸 거의 안풀어봤어서 생긴 문제였다.

 

  dfs로 싸이클 판정하는 부분이 코드의 isCycleExist() 이다. 어찌보면 단순한데, 시작점을 start로 잡고, start부터 무지성으로 dfs 돌려서 다시 start로 되돌아올 수 있으면 싸이클이 있는거다. 주의점은 방문배열을 전체에 대해 잡으면 안되고, 각 노드에서 시작할 때 마다 새로 잡아야 한다(모든 노드 x에 대해 x로 되돌아오는걸 파악해야 하므로).