BFS와 DFS1 [C] 1260: DFS와 BFS 거의 1년만에 자료구조 관련 문제를 푸느라 그런지 정말 오래걸렸다.. 그래도 어찌됐는 풀긴 했는데 일단 잠시 정리를 해봐야겠다 일단 DFS 관련 구현이 훨씬 쉽다. 가장 깊게 들어갔다가 그 노드가 leaf면 바로 뒤로 나오면 되기 때문에 사실상 함수를 만들어 재귀로 만든다면 바로 구현 가능하다. 문제는 BFS인데 얘는 같은 depth인 애부터 먼저 찾아줘야 하기때문에 재귀를 이용해서 푼다면 포인터를 쓰며 굉장히 어렵게 풀어야한다. 구조체를 만들어 서로 link해주면 될 것 같긴한데 사실상 비효율적이다. 이때 BFS와 관련해서 Queue를 하나 만들어주면 front에서는 삭제가, rear에서 삽입이 되면 쉽게 풀 수 있다. 특히 front와 rear이 같아지게 되는 경우는 곧 rear이 더 이상 새로운 값.. 2023. 7. 29. 이전 1 다음