chatterboy   2년 전

안녕하세요.

처음에 단순히 dfs로 탐색하면서 모두 방문되고 v1과 vmn이 인접한 경로를 찾도록 구현을 했는데 시간초과가 뜨고

오일러 서킷인 듯 싶어서 구현을 하긴 했지만 원하는 결과와는 다르게 나와버리네요. 어떻게 방법이 없나요 ?? ㅜㅜ

hahaha   2년 전

n,m이 100이고 모든 정점을 도는 사이클을 찾아야하기 때문에, dfs나 bfs로 탐색해서는 시간초과가 납니다.

n,m이 홀수 또는 짝수일 때의 작은 값들을 넣어, 가능한 경로를 그려보시면, 사이클이 되는 모양을 만드는 일정한 방법이 보이실 겁니다. 

그리드 그래프라 연결되는 모양이 같기 때문에, 규칙을 찾고,그 규칙대로 출력하시면 됩니다. :) 

chatterboy   2년 전

hahaha 아하 ! 감사합니다. :)

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