dfs 검색 결과

해당 글 15건

알고리즘 풀이 - 백준 4963(섬의 개수, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 지도에 섬, 바다가 표시되어 있을 때, 섬의 개수를 구하는 문제. 같은 섬의 기준은 상하좌우대각선으로 연결된 경우 2. 풀이 h x w 크기의 지도가 주어질 때, 1로 표시된 곳은 섬이고 0으로 표시된 곳은 바다이다. 그러므로 현재 탐색 위치의 인접한 섬을 모두 찾아낸다면 그것이 하나의 큰 섬이 된다. 인접한 섬을 찾아낼 수 있는 자료구조는 그래프이다. 인접 행렬로 지도를 저장하고 각각의 위치에서 탐색을 시작하여 이어진 섬 전체의 개수를 찾아내면 된다. 그래프를 탐색해야 하므로 DFS, BFS의 구조를 통해 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 1. 20:52

알고리즘 풀이 - 백준 2667(단지번호붙이기, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 정사각형 모양의 지도에 1은 집이 있고 0은 없는 곳이다. 좌우 / 상하로 이어진 경우에 연결된 모든 집들은 하나의 단지라고 할 때, 각 단지에 있는 집의 수를 오름차순으로 정렬하여 출력하는 문제 2. 풀이 이 문제는 인접한 모든 아파트를 찾아서 하나의 단지로 묶어내야 하는 문제이다. 따라서, 주어진 값이 하나의 행렬 형태로 주어지므로 인접 행렬로 정보를 저장한 뒤 서로 인접한 모든 정점을 찾아 그 개수를 저장한다. 정점을 찾을 때는 DFS 또는 BFS를 이용하여 그래프 탐색을 수행하면 된다. 각 위치에서 탐..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 23:02

알고리즘 풀이 - 백준 1707(이분 그래프, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 이분 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 그래프가 이분 그래프인지 여부를 판별하는 문제 2. 풀이 이분 그래프는 아래와 같이 2 그룹으로 나누었을 때, 같은 그룹은 서로 인접하지 않아야 한다. 위의 그림과 같이 빨간 그룹과 파란 그룹이 있는데 같은 그룹은 인접하여 연결되지 않았다. 이런 경우 이분 그래프라고 할 수 있다. 이를 구하는 방법은 그래프를 탐색하며 인접한 정점들이 같은 속성(보통 색깔로 표현)을 가지지 않는지를 검사하면 된다. 기본적으로 탐색을 수행하면서 현재 탐색 중인 정점의 색상을 지정하고, 그것..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 11:40

알고리즘 풀이 - 백준 11724(연결 요소의 개수, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 그래프 구조에서 연결 요소의 개수를 구하는 문제 2. 풀이 연결 요소란 그래프 상에서 이어져 있는 모든 정점들이 있을 때, 그것을 하나의 연결 요소라고 한다. 예를 들어 아래의 그림을 보자. 위 그래프에서 1, 2, 4는 하나의 연결된 그래프이므로 1개의 연결 요소 이고 3, 5도 하나의 연결된 그래프라서 1개의 연결 요소 이다. 즉, 위 그림에서 연결 요소의 개수는 2개가 되는 것이다. 따라서, DFS, BFS로 2가지 중 1가지의 방법을 사용하여 그래프 탐색을 시도한 뒤 연결 요소의 개수를 구하는 코드를 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 11:39

알고리즘 풀이 - 백준 1260(DFS와 BFS, 그래프(DFS, BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 그래프 형태를 DFS, BFS로 탐색한 결과를 각각 출력하는 문제. 2. 풀이 단순히 양방향 그래프를 DFS, BFS 방식으로 탐색하여 그 결과를 출력하는 방식이다. 이 문제는 인접 정점 중 더 작은 번호를 우선 탐색해야 하기 때문에 인접 리스트로 구현 시, 각 정점과 인접한 정점들의 리스트를 정렬하여 저장하면 작은 번호를 우선 탐색할 수 있게 된다. DFS, BFS의 개념은 상단의 링크를 참조 3. 코드 아래의 코드를 통해 정답을 알아보자. import java.io.*; import java.util.*;..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 11:34

알고리즘 풀이 - 백준 13023(ABCDE, 그래프(DFS))

관련글 그래프 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 친구 관계가 주어질 때, A-B-C-D-E와 같은 관계가 있으면 1을, 없으면 0을 출력하는 문제 2. 풀이 DFS, BFS 등의 그래프 탐색을 통해 친구 관계가 어떻게 이어지는 지 확인하면 된다. A-B-C-D-E와 같은 관계를 찾는 다는 것은 그와 같이 5명이 서로 친구 관계인 경우를 찾으면 된다는 것이다. 따라서 탐색 과정에서 그러한 관계를 찾으면 1을 출력하고 모두 다 탐색이 완료되었음에도 그러한 관계가 없다면 0을 출력한다. 3. 코드 아래의 코드를 통해 정답을 알아보자. import java.io.*; import java.util.*; public class Ma..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 2. 27. 11:32

알고리즘 - 그래프 탐색(깊이 우선 탐색 - DFS)

이번 포스팅에서는 그래프 자료구조의 탐색에 대해서 알아보자. 이전 포스팅에서 배열 / 리스트 형태의 자료구조에 대한 탐색 방법을 알아보았으니 관련 포스팅은 아래 링크를 참고 배열 / 리스트 탐색 : 링크 그래프 자료구조 : 링크 너비 우선 탐색 (BFS) : 링크 1. 그래프 탐색 이전 포스팅의 내용을 잠시 복습해보자. 그래프는 기본적으로 각 정점들이 어떠한 연관 관계를 갖고 있는지를 나타내는 자료구조 이다. 그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고) 해결 가능한 문제들의 예시를 대충 알아보자. 어떠한 것들이 특히 해결이 가능할까? ⓐ 네트워크 : 우리가 사용하는 컴퓨터는 인터넷으로..
자바 프로그래밍/알고리즘(Algorithm) 2020. 12. 8. 23:22