n이 10만이니깐 2^m >= n 을 만족하는 m으로 했을 것 같아요.
혹시 cycle의 최대 노드를 추정할 수 있는 방법이 있나요?
9466번 - 텀 프로젝트
그러니깐 m 번 전진하는게 아니라 2^m 번 전진하는 소스인거죠
https://www.acmicpc.net/problem/3117
이 문제 한번 풀어보세요.
algoshipda
네, 한 번 풀어보겠습니다.
그런데 아직도 잘 이해가 안됩니다.
샘플 input을 예로 들면
3 1 3 7 3 4 6
3 3 3 6 3 7 4
3 3 3 7 3 4 6
...
결국 1,2,3 은 사이클을 돌고 있는 노드를 가리키고 아웃사이더가 됨을 의미하는데요,
왜 이게 2^m 번 움직이는 건지 잘 이해가 되지 않습니다. ㅠㅠ
편의상 a[ i ][ j ] 를 i번째 iteration에서 j번 노드가 가리키고 있는 노드라고 할게요.
자세히 보시면 for 루프는
a[ i+1 ][ j ] = a[ i ][ a[ i ][ j ] ]
이런 식으로 동작합니다.
이 과정에서 a[ i ][ j ] 는 j 에서 2^i 번 전진 했을 때 도착하는 노드가 됩니다.
algoshipda
잘 이해도 못하는데 계속 댓글 달아주셔서 정말 감사합니다.
그 과정에서 왜 2^m인지에 대한 인사이트가 있다고 생각하고 있었는데 맞게 생각한 것인가요?
만약에 1번 노드에서 10번 갔을 때 어디로 가는지와, 다시 그 노드에서 10번 갔을 때 어디로 가는지를 안다면
유튜브 문제는 각 노드에서 2^i 번 갔을 때 어디로 가는지를 알고 있다면, 그걸 적절히 이용해서 k번 가는 경우를 이진수로 표현해서 구할 수 있습니다.
1번 노드에서 20번 갔을 때 어디로 가는지를 알 수 있겠죠?
처음에 주어지는게 각 노드에서 1번 갔을 때 어디로 가는지니깐, 위 과정을 반복하면 2의 거듭제곱꼴로 전진하면 어디로 가는지 구할 수 있을겁니다.
저걸 구하는 이유는 각 노드에서 n번 이상 갔을 때 나오는 노드를 빠르게 구하기 위해서인데요.
사이클에 포함되는 노드는 n번 이상 갔을 때 역시 사이클에 포함된 노드를 가리키게 될거고, 한 사이클 포함된 노드들을 보면 모두 서로 다른 노드를 가리키게 될겁니다.
사이클에 포함되지 않는 노드는 n번 이상 갔을 때 어떤 사이클에 포함이 될겁니다.
이렇게 하면 도착지점에 포함되지 않는 노드들은 사이클에 포함되지 않는다는걸 알 수 있겠죠.
--
유튜브 문제는 각 노드에서 2^i 번 갔을 때 어디로 가는지를 알고 있다면, 그걸 적절히 이용해서 k번 가는 경우를 이진수로 표현해서 구할 수 있습니다.
--
제가 설명을 잘 못하는데.. 혹시 이해 안가시면 말해주세요.
댓글을 작성하려면 로그인해야 합니다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
wooljs 7년 전
cubelover
라는 분의 소스를 봤는데요.
list를 계속 iteration을 돌리면서, cycle을 돌지 않는 노드들은 가리키는 노드들로 수렴하도록 만드는 코드를 짜셨더라고여.
그런데 iteration의 수를 18번으로 특정하셨던데, 이건 trial and error로 찾은 것일까요?
무척 신기해서 오랫동안 들여다봤습니다.
--추가
cycle의 최대 노드수가 아니고 depth 겠군요.