굥뷰를 햡시댜

이전 게시물인 BFS와 마찬가지로 모든 노드에 방문하는 탐색 방법 입니다. DFS도 BFS와 마찬가지로 기본 틀을 알아두시면 코드를 쉽게 작성하실 수 있습니다. 깊이우선탐색(Depth First Search, DFS) DFS는 말 그대로 탐색할 수 있는 끝까지 갔다가 목적지가 아니면 다시 되돌아와서 탐색하는 방법입니다. 가장 쉬운 예로 미로탐색을 들 수 있습니다.(나중에 관련 문제를 풀고 링크를 첨부해드리겠습니다!) 또, DFS는 스택, 반복문, 재귀 같은 방법으로 구현할 수 있습니다. 하지만 여기서는, 재귀에 대한 설명만 하도록 하겠습니다.(가장 많이 쓰이기 때문) 1. 루트 노드를 방문합니다. 2. 우선순위가 가장 높은 자식노드를 방문합니다. 3. 방문한 노드의 자식노드가 있다면 계속 내려갑니다. 4..

안녕하세요 저번 그래프에서 기본적인 탐색방법 중 하나인 BFS에 대해 학습해보려고 합니다. 학습하기 전에 앞서 제가 저는 처음 BFS를 공부할 때 겪었던 어려움에 대해 말하고자 합니다. 저는 처음에 'BFS가 모든 노드를 방문한다는건 알겠는데 코드를 못짜겠네'라고 생각했던 적이 있습니다. 처음 공부하시는 분이시라면 저와 같은 고민을 하시는 분들이 많을 거라고 생각합니다. 그래서 저같은 경우는 BFS를 공부할 때 의사코드를 통째로 외우고 상황에 맞게 코드를 조금씩 수정하는 방식으로 공부했습니다. 개념을 알고 코드를 작성하면서 공부하다보니 BFS가 어떤 방식으로 돌아가는지(?)에 대해 저절로 알게되었습니다. 그렇기 때문에 만약, 코드 작성이 쉽지 않으시다면 의사코드를 먼저 숙지하시고 코드를 짜는 연습을 하시..

- 그래프란 무엇일까요? 그래프라고 하면 '정점(노드)'와 '간선(엣지)'로 이루어진 자료 구조를 말하는데요, 그래프는 간선의 방향 유무에 따라서 단방향 그래프, 양방향 그래프로 나뉩니다. 왼쪽 이미지와 같이 간선이 방향을 나타내면 단방향 그래프, 오른쪽 이미지와 같이 간선이 방향을 나타내지 않으면 양방향 그래프 입니다.(양방향 그래프는 무방향 그래프라고도 합니다.) - 그래프의 표현 방식 그래프를 표현하는 방식으로는 3가지 방식이 있습니다. 1. 간선 리스트(Edge List) (1) 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해 '간선 정보'를 저장합니다. -> ex) 어떤 두 정점 i,j를 연결하는 간선 (i,j)를 간선 리스트 배열 A에 저장했을 경우 A[k][0] = i, A[k][1..