WORDCHAIN에서 오일러 패스 활용법 막히네요;; coldradio 안녕하세요. WORDCHAIN 문제입니다. dfs로 풀어보니 시간초과가 나오더라구요;; 그래서 검색하다 오일러 패스/서킷을 이용할 수 있다는 걸 알게 되었습니다. 하지만 어떻게 오일러 패스 문제와 연결될 수 있을까가 잘 모르겠더라구요. 예를 들면, A <-- --> B <-- --> C 와 같이 3개의 노드가 있고, AB사이 BC사이 패스가 2개씩 총 4개 있습니다. 그러면 오일러 써킷은 존재하죠. B-->A-->B-->C-->B. 위 예는 A-->B-->C로의 WORDCHAIN에 대한 답도 존재하는데요. 오일러 써킷이랑, A-->B-->C랑 어떻게 연결시켜서 풀어야 할까요?;; 감사합니다.! 8년 전
0개의 댓글이 있습니다. 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
coldradio
안녕하세요.
WORDCHAIN 문제입니다.
dfs로 풀어보니 시간초과가 나오더라구요;; 그래서 검색하다 오일러 패스/서킷을 이용할 수 있다는 걸 알게 되었습니다.
하지만 어떻게 오일러 패스 문제와 연결될 수 있을까가 잘 모르겠더라구요.
예를 들면,
A <-- --> B <-- --> C
와 같이 3개의 노드가 있고, AB사이 BC사이 패스가 2개씩 총 4개 있습니다.
그러면 오일러 써킷은 존재하죠. B-->A-->B-->C-->B.
위 예는 A-->B-->C로의 WORDCHAIN에 대한 답도 존재하는데요.
오일러 써킷이랑, A-->B-->C랑 어떻게 연결시켜서 풀어야 할까요?;;
감사합니다.!
8년 전