코드업 5012 : 메시지 전달

문제링크

메시지 전달

이 문제는 백준에는 없는 듯하다.

그래서 코드업 얘기를 하자면, 이 문제를 통과한 유저는 100명이 채 되지 않는다! (당시기준)

맞춘 유저가 100명이면 코드업 중에서는 주로 조금 어려운 문제에 속하지만, 이 문제는

생각만 잘하면 쉽게 풀리는 문제이다!

 

풀이

핵심은 이것이다.

확정할 수 있는 'loopy' 하지 않은 소가 메시지를 전달해야 하는 소는 없다.

또한 'loopy'한 소에게 메시지를 전달하는 소도 'loppy'하다.

 

예를 들어, 5 0 4 1 5 4 와 같이 입력된다고 할 때,

확정할 수 있는 'loopy' 하지 않은 소는 1번 소이다. (가리키는 소가 0이기 때문)

 

그 다음부터는 loopy 하지 않은 소에게 메시지를 전달하는 소를 찾으면 된다.

예를 들어, A는 loopy 하지 않은 소이다. B는 A를 가리킨다. C는 B를 가리킨다.

이 경우, loopy 하지 않은 소는 A와 B 뿐만 아니라, C도 loopy 한 소가 아니다.

때문에, loopy 하지 않는 소를 가리키는 소를 찾는것을 넘어서, 그 'loopy 하지 않은 소를 가리키는 소'를 가리키는 소도 찾아야 된다. 때문에, 그 ''loppy 하지 않는 소를 가리키는 소'를 가리키는 소'도 찾아야한다.

 

이 행위를 하기 위해서는 반복문으로 반복을 N번 반복하면서 계속 탐색을 해주어야 한다.

그 N번 탐색하면서 해야할 일은, 모든 소를 탐색하며 '해당 소가 가리키는 소가 loppy 한 소인가? (0인가? <-- loopy한 소의 번째수의 인덱스는 0으로 저장하기 때문)

이를 코드로 나타내면 if(a[a[j]]==0) 인데 복잡할 수 있으니 풀어서 설명해보겠다.

여기서 a[j]는 해당 소가 가리키는 소의 값이다. 그러니 a[j]번째 소가 가리키는 소의 값이 0이면 loppy 한 소이다.

여기서 a[j]번째 소가 가리키는 소를 코드로 나타내면, a[ a[j] ] 가 되겠다.

 

지금까지 말한 내용들을 코드로 구현하면 다음과 같다.

코드로 글을 마친다.