백준 11725. 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

bfs를 이용해서 풀었다.

큐를 다음과 같이 

queue<pair<int,int>> q

로 int형 한 쌍이 들어가도록 pair로 선언하고 

{ 정점, 이전정점 } 을 기록해서 각 정점이 어떤 정점에서 이동되었는지 기록한다.

 

이렇게 기록하면 이전 정점이 현재 정점의 부모가된다.

 

 

다른 분들 코드를 봤는데 큐를 페어로 선언 하지 않아도 된다.

생각해보면 그냥 이전 정점이 현재 정점의 부모이다..

 

---

python

 

파이썬으로 풀어봤는데 아무리 봐도 시간초과가 날 코드가 아닌데 계속 시간초과가 나서 검색해봤다.

이런경우 queue가 deqeue보다 훨씬 느리단것을 알게 됐다.

 

https://www.acmicpc.net/board/view/38423#comment-70882

글 읽기 - 시간 보너스를 제거해 주세요.