백준 dfs

문제를 풀기 전 그래프 및 DFS 개념이 부족하다면 아래 포스팅을 먼저 읽어주세요! https://sunro1994.tistory.com/179 [자료구조 - Graph 와 DFS] Graph와 DFS란? [Algorithm] 깊이 우선 탐색 목차 1. DFS란? 2. 그래프란? 그래프의 특징 그래프의 종류 그래프 용어 1. DFS란? 깊이 우선 탐색(Depth-First-search)은 그래프 완전 탐색 기법중 하나 그래프의 시작 노드에서 sunro1994.tistory.com 문제해결중 놓친 중요한 부분 - 내림차순! Do it 알고리즘 자바편을 통해 DFS를 공부하고 해당 코드를 변경해서 이 문제를 풀려고 했다. 책에서 제공했던 백준 문제는 아래의 문제였다. https://www.acmicpc.ne..

위 문제는 DFS풀이의 가장 기본적인 문제이다. 문제를 풀기에 앞서 풀이 순서를 짚어보자. 1. 최대 정점의 개수와 문제풀이 시간을 대조해본다. - 문제 풀이 시간은 3초이다. 최대 노드의 개수는 1000개로 n^2의 복잡도로 문제를 풀어도 충분히 시간이 남는다. 2. 해당 그래프를 직접 그려본다. - 첫 예시의 그래프를 만들어보자면 다음과 같다. (혼을 담아 정성스럽게 그려보았다) 3. 이처럼 두개의 그래프가 그려지는것을 확인할 수 있다. 이를 코드로 작성하기 위한 슈도코드를 작성해본다. n(노드 개수) , m(엣지 개수) A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열) for(n만큼 반복 {A 인접 리스트의 각 ArrayList초기화} for(m의 개수만큼 반복하기) { A..