자료구조+알고리즘/BFS와 DFS 썸네일형 리스트형 [1260][java][백준]DFS와BFS 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 풀이 테스트 케이스 대로 숫자를 입력받으면 어떤 그래프가 나오는지 보겠습니다. 테스트 케이스 상으로는 노드 1 부터 시작하게 됩니다. DFS: 1 - 2 - 4 - 3 BFS: 1 - 2 - 3 - 4 * 간선들의 연결이 되어 있는지 혹은 되지 않았는 것을 판단하는 것이 인접행렬을 이용하거나, 혹은 인접리스트를 이용하는 것이 좋습니다. 1) 인접 행렬 1번 꼭지점이 n번 꼭지점과 연결이 되어 있으면 1로 처리, 연결이 되어있지 않은 선은 0으로 처리 단점> 꼭지점의 갯수(Vertex)가 적을 때만 가능하다는 점. 갯수가 많아질수록 탐색 시간이 오래 걸림 2) 인접리스트 자신의 노드에서 갈 수 있는 노드를 가지고 있다고 생각하면 쉽습니.. 더보기 이전 1 다음
