이번 글은 삼성 코테 기출 문제인 19238번 문제를 복기하면서 쓰는 글이다.https://www.acmicpc.net/problem/19238 해당 문제는 문제설명에서도 나와있듯이, 택시가 승객이 위치한 곳으로 이동해야하며 이때 택시의 위치에서 가장 가까운 위치에 있는, 즉 최단경로에 있는 승객을 태우러 가기 때문에 BFS 알고리즘을 떠올려야 했다. + 조건을 잘 따져가면서 풀어야 하는게 중요했다. 해당 문제는 눈높이 개발에서 진행하는 코딩테스트 챌린지를 진행하면서 푼 문제인데, 여기서 힌트를 주신게 메모리 초과가 나지않게 점검해보라고 하셨던 거였다! 그래서 처음에 딱 생각이 났던게, 택시와 승객의 최단 경로 길이를 구해야하는데 이걸 승객마다 BFS를 돌리기에는 시간초과가 뜰 것 같다는 생각이 들었다..
BFS
*이것이 취업을 위한 코딩테스트다 with 파이썬 교재를 공부한 내용을 바탕으로 작성했습니다. DFS (Depth-First Search) : 깊이 우선 탐색, 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하며 스택 자료 구조 이용, 재귀호출 알고리즘도 같이 많이 사용한다! 모든 노드를 방문하고자 할 때 BFS (Breadth-First Search) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘이며 큐(선입선출)를 이용한다. 두 노드 사이의 최단 경로 ex) 최단거리 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 ..
