(백준 1260) 큐 사용에 대해서 질문드립니다!

Question

선생님 덕분에 회차를 거듭할수록 재귀에 대한 이해도가 높아지고 있습니다 감사합니다! 기존에 계속 독학으로 하다보니 제가 아는 내용과 조금 다른 부분이 있어 오늘만 벌써 두번째 질문이네요 ㅜㅜ 기존에 큐를 구현할때 Queue q = new LinkedList<>(); 혹은 PriorityQueuepq = new PriorityQueue<>(); 로 구현해서 사용했었습니다! 근데 혹시 ArrayList로 구현하시는 이유가 있을까요?? 하나 더 여쭤보자면... dfs는 재귀함수를 호출하는게 필수인데 비해 bfs는 재귀호출이 없는데 그럼 bfs는 재귀가 아닌 queue를 무조건적으로 사용한다고 생각하면 될까요? 매번 훌륭한 강의 감사드립니다!!

개발자로 취직하기 · Answer

이번에도 너무 좋은 질문이네요! 저도 강의나 설명을 들을 때 질문을 많이 하는 편인데, 질문하는 만큼 더 집중하게 되고 이해가 잘되는 것 같아서 조금이라도 궁금한 부분은 꼭 질문 남겨주세요! Queue를 왜 ArrayList로 정의했는가 우선 말씀하신 LinkedList나 Priority Queue를 사용해도 동일하게 문제를 풀 수 있어서 어떤 방식을 사용해도 무방합니다. 다만 제가 ArrayList를 사용한 건, 최대한 외워야 할 기본 라이브러리/클래스의 수를 줄이기 위해서에요. 결국 BFS를 하면서 필요한 건 맨 뒤에 요소를 추가하고 맨 앞의 요소를 꺼내오는 동작, 이 2가지이기 때문에 이 동작을 제공하는 자료구조라면 뭐든 사용이 가능합니다. 그런데 Queue나 PriorityQueue를 사용하려고 하다보면, 어떤 자료구조는 add/remove 함수를 써야 하고, 또 누구는 poll/peek를 써야 해서 어느 자료구조 하나도 제대로 사용하지 못하는 경우가 자주 발생하는 것 같아요. 그래서 제 강의나 코딩 테스트 문제를 풀 때 되도록 ArrayList와 같이 가장 기본적이고 보편적으로 많이 사용되는 자료 구조로 통일하려고 합니다! DFS == 재귀 && BFS == Queue? 말씀하신 대로 DFS는 재귀함수, BFS는 Queue로 구현하는 것이 가장 일반적이라 BFS 유형에서는 queue를 사용한다고 생각하시면 됩니다! BFS 강의도 최대한 빨리 준비해서 깔끔하게 정리해볼게요 :)