엔지니어 동행하기

DFS문제에서 어려울 수 있는 부분은 재귀함수의 동작 원리를 알아야만 문제를 풀 수 있다는 점 입니다. DFS 알고리즘에서 어떻게 재귀함수를 활용하는지를 중점으로 설명드리겠습니다. 기본구조 & 탐색과정 def dfs(v): //O(E) 백트래킹 관계없이 v 방문 시 수행할 코드 if visited[v] ==1: //백트래킹 조건 return visited[v] =1 //(깊이 탐색하기 전 v 에서 수행할 코드) if/for 추가적인 탐색 조건 //탐색 우선순위가 높은 경우 dfs(i) for i in graph[v]: //인접노드 탐색 dfs(i) //깊이 탐색한후 v에서 수행할 코드 기본이 되는 DFS 코드를 분석하면 3부분으로 나눌 수 있습니다. if문(백트래킹 조건) 방문한 노드에서 수행할 코드 f..

그래프 탐색 BFS 문제를 처음 접했을 때 어려울 수 있는 점은, BFS 문제에 좌표에 대한 내용이 많이 나오는데 이를 그래프 개념과 연결시키는 부분입니다. 카카오 코딩 테스트 문제(KAKAO BLIND RECRUITMENT 2019~2021)를 직접 풀어보며 이에 대해 정리했던 내용을 공유합니다. 기본 구조 from collections import deque def bfs(start): global n dist = [math.inf] * n q = deque([]) q.append(start) dist[start] = 0 while q: node = q.popleft() for i in graph[node]: # nextCost 계산 if nextCost < dist[i]: q.append(i) di..