![]()
이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다. 자바를 활용하다 보면 그래프나 트리 구조를 탐색해야 할 때가 있습니다. 예를 들어, 네트워크 경로 탐색, 웹 크롤링, 게임 AI 에서의 경로 탐색 등 다양한 분야에서 이러한 탐색 알고리즘이 사용됩니다. 이때 사용할 수 있는 것이 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)입니다. 이 두 알고리즘은 그래프나 트리 구조에서 특정 노드를 찾거나, 모든 노드를 방문하는 데 유용합니다. DFS(Depth-First-Search)란❓Depth-First-Search를 번역해보면, 깊이 우선 탐색입니다. DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 이름에서 알 ..
![]()
그래프는 많은 컴퓨터 과학 문제에서 필수적인 데이터 구조입니다. 그래프를 사용하면 복잡한 네트워크 구조를 모델링하고 다양한 문제를 해결할 수 있습니다. 예를 들어, SNS에서 친구 관계를 나타내거나, 도로망에서 최단 경로를 찾는 문제 등을 해결할 수 있습니다. Graph란 ❓Graph는 객체 또는 개체 간의 관계를 표현하는 자료구조입니다. 객체(Node)들 간의 연결(Egde)로 구성됩니다. Graph의 정의그래프는 두 가지 주요 구성 요소로 이루어집니다. 노드(정점, Vertex)그래프에서 개별적인 객체 또는 노드를 나타냅니다.간선(엣지,Edge)노드 간의 연결을 나타내며, 노드 간의 관계를 정의합니다.그래프는 노드와 간선의 집합으로 표현되며 다음과 같이 표현됩니다.G = (V,E)G : Grap..
![]()
문제설명입력 & 출력 나의 풀이 이번 문제는 DFS와 BFS를 활용하여 주어진 정점 V로부터 탐색하는 정점을 출력하는 문제입니다. DFS와 BFS에 대한 개념이 있으시다면 어렵지 않게 풀 수 있는 문제였습니다. 먼저 가독성을 위해서 전역변수로 사용할 수 있는 변수들은 전역변수로 선언해 줍니다. main문 먼저 설명하자면, 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer를 사용하여 간선이 연결하는 두 정점의 번호를 공백을 기준으로 분리를 해줍니다. 그리고 입력받은 정점의 크기만큼 정점을 나타내는 graph배열을 초기화해 줍니다. 이때 문제에서 나왔듯이 정점은 1부터 시작하기 때문에 "+1"을 해줘야 합니다. 그리고 간선의 개수 M만큼 반복하는..
![]()
문제설명입력 & 출력 나의 풀이 컴퓨터의 개수 N과 각 컴퓨터 간의 연결 상태를 나타내는 2차원 배열 computers가 주어질 때 서로 연결된 컴퓨터들을 하나의 네트워크로 간주하고 전체 네트워크의 개수를 리턴하는 문제입니다. 해당 문제는 DFS로 연결된 노드들을 쉽게 찾을 수 있습니다. 먼저 Solution에서는 입력으로 주어지는 컴퓨터의 개수 n과 연결에 대한 정보 배열인 computers를 인자로 받습니다. 입력받은 컴퓨터의 개수만큼 노드가 있어야 하기 때문에 n만큼의 크기를 가지는 visited배열을 초기화를 해줍니다. 연결된 네트워크의 개수를 0으로 초기화해주고, 모든 노드들을 순회하는 반복문을 선언합니다. 만약 해당 노드가 아직 방문하지 않은 노드라면, dfs를 수행하여 해당 네트워크의 모든 ..
