yukariko   2년 전

유턴을 하지 않으면서 사이클을 돌아야해서 일단은 dfs 로 구현했습니다.

그런데 visit 체크를 하자니 사이클을 돌때 왔던길을 다시가야하는 경우가 생기고

안하자니 작은 사이클안에서 빙빙 돌고..

어떻게 구현해야 할까요? 힌트 좀 부탁합니다..

pichulia   2년 전

visit 배여ᆢ을 [n][m] 이 아니라 [4][n][m]으로 만들어보세염

개꿀

amugeona   2년 전

1. 사이클을 하나의 큰 정점으로 본다. (일반 길은 작은 정점)

2. 하나의 큰 정점에서 출발해서 다른 큰 정점으로 도착할 수 있다면, 해당 길에 위치하는 모든 작은 정점들은 제법 괜찮은(?) 녀석들이다.

3. 주어진 방법으로 방문할 수 없는 작은 정점들이 존재한다면, 막다른 길이 있단 뜻이다.

이런 생각으로 보면 SCC로 풀수 있지 않을까요? 이렇게까지 풀어야되나 의혹은 있지만...?

yukariko   2년 전

두분의 말씀을 듣고 지금 뭔가 유레카! 한거같은 느낌이긴한데 자세한건 풀어봐야 알거같습니다 ㅋㅋ

답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.