너비우선탐색3 DFS/BFS 개념 및 문제 접근 방법 0. 개요 - DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. - DFS와 BFS가 어떻게 다른지, 언제 사용되는지 알아보자. 1. DFS(Depth First Search) a) DFS의 탐색 방법 - DFS는 다음과 같은 탐색 순서를 갖는다. - DFS는 하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다. ▶ 트리의 경우, 왼쪽에 위치한 노드를 우선적으로 탐색한다. ▶ 그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다. - 위의 그림을 토대로 DFS는 다음과 같은 탐색 순서를 갖는다. ▶ 0번을 시작으로 왼쪽에 위치한 노드를 우선적으로 탐색한다. (0 ~ 3번 노드로 탐색) ▶ 3번 노드가 끝이므로 이전 단계로 돌아간다. (1번 노드로 돌아감) ▶ 1번 노드에서.. 2022. 7. 5. LeetCode 994(Rotting Orange, java) 0. 문제 https://leetcode.com/problems/rotting-oranges/ Rotting Oranges - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 문제 설명 - 문제에서 이중 배열(grid)이 주어진다. - 이중 배열에는 빈 공간(= 0), 신선한 오렌지(= 1), 상한 오렌지(= 2)와 같은 3가지 값이 저장되어있다. - 상한 오렌지에 인접한 신선한 오렌지는 1분이 지날 때마다 상한다. - 인접한 오렌지 중 상한 오렌지가 존재하.. 2022. 5. 6. Advanced Algorithm - 너비 우선 탐색(Breadth First Search) 1. 그래프 탐색 알고리즘이란? - 그래프를 기반으로 특정 노드를 찾아가기 위한 알고리즘 - 이 그래프 알고리즘에는 2가지 대표 알고리즘이 있다. 너비 우선 탐색(Breadth First Search) - 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search) - 정점(노드)의 자식노드를 먼저 탐색하는 방식 a) 너비 우선 탐색(BFS)의 예 - 방향과 상관없이 왼쪽 또는 오른쪽 노드를 기준으로, 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드(형제 노드)를 먼저 순회하는 탐색 BFS 이동순서: A - B - C - D - G - H - I - E - F - J b) 깊이 우선 탐색(DFS)의 예 - 방향과 상관없이 왼쪽 또는.. 2020. 9. 24. 이전 1 다음
