본문 바로가기

BFS2

[WEEK03] 개발일지 (부제: set💖과 소소한 행복 찾기) ※ 개발일지가 아니라 일기일 수도 있는 점 양해바랍니다. 오전, 오후, 새벽이 모두 담겨있어요.※ ※ WEEK 시작인 매주 목요일에 업데이트 됩니다. 많.관.부 ※ DAY01 22.10.06 (목) from Jungle import Knowledge 벌써(?) 3주차이다. 사실 일주일 됐을 때 2주를 체감했고, 2주가 됐을 때 4주를 체감했는데 돌이켜보니 일단 했다. 이번 시험은 B반이 먼저 시험을 봤고, 문제는 쿼드트리, PPAP, 소수곱이 나왔다. 저번 주에 색종이 만들기를 공부하면서 힌트에 '쿼드트리를 만드는 문제'라고 해서 '쿼드트리가 뭐냐!!' 하면서 혼자 공부를 했었는데 문제에 나와서 반가웠다. 하지만, 공부를 하지 않았다면 과연 풀 수 있었던 문제일까 생각해보면 잘 모르겠다.. 아직 재귀에 .. 2022. 10. 13.
[알고리즘] BFS 뿌셔 DFS 뿌셔 BFS - BFS = Breath-First Search - 가까운 노드부터 우선 탐색 : s로부터 거리가 k+1인 한 정점을 만나기 전에, s로부터의 거리가 k인 정점을 모두 발견하는 알고리즘 (CLSR에 적힌 정의) - 큐 자료구조를 이용: 1. 탐색 시작 노드를 큐에 삽입, 방문 처리 => Queue에 들어있는 애들 = frontier 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 => frontier 갱신 1) 큐에서 popleft() (popleft()한 값 u / deque이기 때문에 popleft()를 통해서 큐의 맨 앞 요소를 빼줌) 2) u의 인접 노드 v 를 방문했는지 확인 3) 방문 안 했으면 큐에 v 삽입 + v의 dist.. 2022. 10. 10.