그래프6 [알고리즘] DFS & BFS 목차 DFS (깊이 우선 탐색) DFS (Depth-First Search)는 깊이 우선 탐색이라고도 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 재귀나 스택을 이용해서 구현을 한다. DFS를 구현할 때 어떤 노드를 방문했었는지 꼭 검사를 해야 한다. 왜냐하면 이를 검사하지 않을 경우 무한루프에 빠질 수 있기 때문이다. 보통 모든 노드를 방문하고자 할 때, DFS를 이용한다. 하지만, 검색 속도는 보통 BFS보다 느리다. 구현 방법 : 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 위의 1번.. 2022. 5. 23. [알고리즘] 플로이드 와샬 (Floyd Warshall) 목차 플로이드 와샬이란? 다익스트라 알고리즘은 하나의 노드에서 출발했을 때 다른 모든 노드로의 최단 경로를 구하는 알고리즘이다. 하지만 플로이드 와샬 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 구하는 알고리즘이다. 그리고 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택을 해서 그 적은 비용을 가지는 노드의 인접한 노드들로 가는 비용을 하나씩 계산하는 방식이었다면 플로이드 와샬 같은 경우는 거쳐가는 노드를 기준으로 알고리즘을 수행한다는 특징이 있다. 추가로 플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드 간 최소의 비용을 계산한다. 플로이드 와샬 예시 위와 같은 그래프가 있다고 가정해 보겠다. 그리고 각각의 노드에서 다른 노드로 가는 비용을 2차원.. 2022. 5. 21. [백준] 1697번 : 숨바꼭질 – JAVA [자바] https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 문제 풀이 백준 1697번 숨바꼭질은 그래프, 그중에서도 BFS를 써서 푸는 난이도 실버 1의 문제이다. 왜 BFS를 쓰냐면 BFS는 Queue를 이용해서 count를 구하기 쉽지만 DFS는 재귀 함수로 구현되기 때문에 카운트를 구하기가 쉽지가 않다. 이 문제에서는 수빈이의 위치 n, 그리고 동생의 위치 k가 주어진다. 그리고 수빈이의 위치가 X이면 1초 후에 X-.. 2022. 2. 11. [백준] 2583번 : 영역 구하기 – JAVA [자바] https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀이 방법 이 문제는 전형적인 영역의 개수를 구하는 그래프 문제이다. 이런 문제 유형이 많으므로 조금만 풀면 이 유형의 그래프 문제는 쉽게 풀 수 있을 것이다. 조금 더 많은 그래프의 정보를 원한다면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/자료구조-그래프 Graph [자료구조] 그래프(Graph) 목차 그래.. 2022. 2. 4. 이전 1 2 다음 반응형
