백준 1012: 유기농 배추 (Swift) - BFS구현 시 pop을 할까 말까?

이전에 포스팅했던 적 있는 간단한 DFS 혹은 BFS 문제입니다.

 

조금 다른 풀이방식으로 구현을 했기에 다시 한 번 포스팅을 하게되었습니다..

 

기존 알고리즘 풀이는 항상 Python으로 진행하다가, IOS개발자로서 본격적으로 코딩 인터뷰를 대비하게 되며 Swift로 알고리즘을 구현하게 되었고, 처음 BFS를 구현해보면서 배운 방법은

 

- BFS의 queue의 맨 앞 원소를 "Pop"하지 않고, 현재 맨 앞을 나타내는 Index를 정수 변수로 두어 q.count > Index인 동안만 while문을 돌리는 것이었습니다.

 

이는 실행시간 면에서는 더 빠를 것입니다 ( Array의 원소를 없애는 과정이 생략되었으므로 )

 

하지만 많은 데이터를 q에 담아야하는 경우에는 메모리 초과가 날 수 있겠죠....

 

이러한 생각을 하던 중, 다른 Swift알고리즘 코드에서 q.removeFirst() ( -> queue의 맨 앞 원소를 삭제하고 return)를 사용한 BFS풀이를 보게되었고, 이 둘의 소요시간을 비교해보고싶었습니다.

 

아래는 차례로 Index, removeFirst()를 사용한 BFS풀이 소요시간입니다.

 

이 문제가 그닥 입력이 많은 문제가 아니라서 실행시간에는 차이가 나지 않았습니다. 

추후에 다른 BFS문제에서 유의미한 시간차이가 난다면 다시 포스팅을 해보겠습니다..

여러분들이 같은 문제에 대해 비교를 해보신 경험이 있으시다면 공유 부탁드립니다 ^^