인프런 커뮤니티 질문&답변
작성한 질문수
(백준 1260) 큐 사용에 대해서 질문드립니다!
해결된 질문
작성
·
270
1
선생님 덕분에 회차를 거듭할수록 재귀에 대한 이해도가 높아지고 있습니다 감사합니다!
기존에 계속 독학으로 하다보니 제가 아는 내용과 조금 다른 부분이 있어 오늘만 벌써 두번째 질문이네요 ㅜㅜ
기존에 큐를 구현할때
Queue<Integer> q = new LinkedList<>();
혹은
PriorityQueue<Integer>pq = new PriorityQueue<>();
로 구현해서 사용했었습니다!
근데 혹시 ArrayList로 구현하시는 이유가 있을까요??
하나 더 여쭤보자면...
dfs는 재귀함수를 호출하는게 필수인데 비해
bfs는 재귀호출이 없는데
그럼 bfs는 재귀가 아닌 queue를 무조건적으로 사용한다고 생각하면 될까요?
매번 훌륭한 강의 감사드립니다!!
답변 1
2
이번에도 너무 좋은 질문이네요! 저도 강의나 설명을 들을 때 질문을 많이 하는 편인데, 질문하는 만큼 더 집중하게 되고 이해가 잘되는 것 같아서 조금이라도 궁금한 부분은 꼭 질문 남겨주세요!
Queue를 왜 ArrayList로 정의했는가
우선 말씀하신 LinkedList나 Priority Queue를 사용해도 동일하게 문제를 풀 수 있어서 어떤 방식을 사용해도 무방합니다. 다만 제가 ArrayList를 사용한 건, 최대한 외워야 할 기본 라이브러리/클래스의 수를 줄이기 위해서에요. 결국 BFS를 하면서 필요한 건 맨 뒤에 요소를 추가하고 맨 앞의 요소를 꺼내오는 동작, 이 2가지이기 때문에 이 동작을 제공하는 자료구조라면 뭐든 사용이 가능합니다. 그런데 Queue나 PriorityQueue를 사용하려고 하다보면, 어떤 자료구조는 add/remove 함수를 써야 하고, 또 누구는 poll/peek를 써야 해서 어느 자료구조 하나도 제대로 사용하지 못하는 경우가 자주 발생하는 것 같아요. 그래서 제 강의나 코딩 테스트 문제를 풀 때 되도록 ArrayList와 같이 가장 기본적이고 보편적으로 많이 사용되는 자료 구조로 통일하려고 합니다!DFS == 재귀 && BFS == Queue?
말씀하신 대로 DFS는 재귀함수, BFS는 Queue로 구현하는 것이 가장 일반적이라 BFS 유형에서는 queue를 사용한다고 생각하시면 됩니다! BFS 강의도 최대한 빨리 준비해서 깔끔하게 정리해볼게요 :)
늦은 시간에도 확인해주시고 답변 달아주셔서 정말 감사합니다!
도움이 많이 됐습니다!