dfs
-
[그래프, BFS&DFS] 1260, 2606 문제 풀이Dev/알고리즘 2020. 8. 26. 17:36
두 문제 다 DFS와 BFS, 그래프에 대한 개념 문제라고 생각한다. 1260 문제 풀이 그래프는 인접 리스트, 인접 행렬로 나누어짐 인접 리스트는 각 원소 별로 인접해 있는 주변 원소들을 각 원소와 연결시킨 리스트로 표현하는 것. 인접 행렬은 배열을 선언해 전체 배열 중 인접 원소들을 true 변환하는 것이라고 볼 수 있음. 인접 행렬로 문제를 푼 결과는 해당 페이지에서 확인 가능하다. github.com/saturdayAlgo/acmicpc/blob/master/sw/java/p01260/array/Main.java saturdayAlgo/acmicpc Contribute to saturdayAlgo/acmicpc development by creating an account on GitHub. gi..
-
[알고리즘] DFS와 BFS 정리Dev/알고리즘 2020. 6. 12. 01:53
DFS: Depth First Search 깊이를 우선으로 하는 검색 방법이다. 재귀 함수, 스택으로 구현한다. BFS: Breadth First Search 너비를 우선으로 하는 검색 방법이다. 큐로 구현한다. 위의 그림은 7을 찾아가는 과정을 DFS, BFS로 표현한 그림이다. DFS는 빨간색으로, BFS는 파란색으로 그려봤다. DFS는 tree의 level과 관계 없이 최상단(1)부터 각각의 leaf node까지를 찾아본 후, 다음 leaf node까지를 계속해서 검색하다 7이 나오면 종료한다. BFS는 같은 level의 node들을 모두 검색하고, 검색한 node들의 하위 node들을 검색하는 방식으로 작업이 수행된다. 그래서 DFS의 경우 5번, BFS의 경우 6번만에 7을 찾아 작업을 종료했다.