BFS
-
코딩 테스트 - 그래프(Graph)의 개념과 문제Coding Test/Coding Test 문제 추천 2021. 9. 26. 14:17
그래프(Graph) 그래프란? ㆍ 정점(Vertex)과 간선(Edge)으로 구성된 자료구조이다. 그래프 탐색 문제 난이도(하) ㆍ 백준 1260번 : DFS와 BFS (🥈 실버 2 티어) ㆍ 백준 2667번 : 단지번호붙이기 (🥈 실버 1 티어) ㆍ 백준 1012번 : 유기농 배추 (🥈 실버 2 티어) ㆍ 백준 11724번 : 연결 요소의 개수 (🥈 실버 2 티어) ㆍ 백준 4963번 : 섬의 개수 (🥈 실버 2 티어) ㆍ 백준 3184번 : 양 (🥈 실버 2 티어) ㆍ 백준 2606번 : 바이러스 (🥈 실버 3 티어) ㆍ 백준 11403번 : 경로 찾기 (🥈 실버 1 티어) ㆍ 백준 11725번 : 트리의 부모 찾기 (🥈 실버 2 티어) 난이도(중) ㆍ 백준 2251번 : 물통 (🥈 실버 1 티어) ㆍ..
-
BFS(너비 우선 탐색)Computer Science/Algorithm 2021. 9. 25. 11:02
BFS란? ㆍ DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다. ㆍ 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. ㆍ 스택 자료구조를 통해 구현할 수 있다. BFS의 그래프 순회 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; boolean marked; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.marked = false; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; fo..
-
DFS(깊이 우선 탐색)Computer Science/Algorithm 2021. 9. 25. 10:57
DFS란? ㆍ DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다. ㆍ 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. ㆍ 스택 자료구조를 통해 구현할 수 있다. DFS의 그래프 순회 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; boolean marked; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.marked = false; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; fo..