그냥 개발블로그에요

알아보기 Breadth-First Search 너비 우선 탐색이다. 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. BFS 는 재귀적으로 동작하지 않는다. 위의 그림에서도 볼 수 있듯이, 같은 레벨에 있는 노드들을 방문한 뒤 다음 레벨의 노드들을 방문하는 방식이다. 노드들은 큐에 집어넣어, 레벨이 바뀌면 뺀다. 이 과정은 아래의 그림을 통해 이해해 볼 수 있다. 적용하기 미로의 최단거리, 그래프 최단거리등 최단거리를 구하고자 할 때 사용된다. 말단 노드까지의 가장 짧은 경로를 구해보자. import java.util.LinkedList; import java.util.Queue; class Node{ int data; Node2 lt, rt; public Node2(int val){ da..

알아보기 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정점은 노드, 간선은 노드를 연결하는 선으로 생각하면 된다. 그렇다고 해서 노드 간 부모 자식이라는 관계는 존재하지 않고 그냥 연결관계만 나타낸다. Tree와 비슷하지만, 그래프는 간선이 없는 노드도 존재한다는 점에서 차이를 나타낸다. 탐색방법 그래프 탐색이란 하나의 정점으로 부터 모든 정점들을 한번씩 방문하는 행위를 뜻한다. 예를 들어 섬끼리 이동할 수 있을지, 이동할 수 있다면 시간이 얼마나 걸리는지 등의 예시에서 사용될 수 있다. 어떤식으로 방문해야 할까? 여기서 두가지 방법이 있다. DFS 깊이 우선 탐색 BFS 너비 우선 탐색 구현 인접 행렬과 인접리스트 방식으로 구현할 수 있다. 인접행렬 2차원 배열 안에 모든 정점들의 ..