늦깎이 IT

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1 오늘은 지난시간에 이어 DFS와 BFS를 코드레벨에서 살펴보겠습니다.우선, 정점의 연결관계를 나타내는 가장 대표적인 방법은 인접 행렬과 인접 리스트로 나뉩니다. 1. 인접 행렬 위와 같은 노드와 간선을 연결하는 그래프가 있다고 가정하겠습니다.이 그래프의 연결 정보를 인접 행렬로 표현한다면 어떻게 해야할까요???? 결론부터 말씀드리면 아래 그림과 같은 2차원 배열에 연결 정보를 저장할 수 있습니다. 이 2차원 배열이 뜻하는 바를 살펴보면 행과 열의 데이터가 1이면 해당 노드들이 ..

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 우선, 그래프는 정점과 간선으로 이루어진 자료구조라고 할 수 있습니다.아래 그림을 살펴보겠습니다. 이 그림에서 동그라미로 표시된 1부터 6까지는 정점(Vertex) 라고 불리며, 각 노드를 연결하는 직선을 간선(Edge)이라고 합니다. (포스팅에서는 정점을 노드라고 칭하겠습니다.....제가 좀 익숙해서) 너비우선탐색(BFS)와 깊이우선탐색(DFS)는 어느 한 노드로부터 시작해서 원하는 노드로까지 탐색하는 방법을가르키는 알고리즘이라고 할 수 있습니다. 1. 너비우선탐색(BFS)너비우선탐색은 말그대로 현재 노드와 인접한 노드들부터 탐색하는 방법입니다.예를 들..

[백준 1260번] DFS와 BFS 소스 코드입니다. [백준 1260번 URL]https://www.acmicpc.net/problem/1260 DFS와 BFS의 기본 개념을 알고 싶으신 분은 클릭해주세요.2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1 1. 각 노드간의 연결 상태는 vector에 저장한다.예를 들어, 0번 노드와 연결된 경우 graph[0]에 차곡차곡 저장한다.즉, 0번 노드와 연결된 노드의 갯수는 graph[0].size()이다. 2. 각 노드간의 연결상태를 저장했다면 visited 배열을 통해 차근차근 방문한다.반복문을 통해 graph[0]부터 차근차근 접근한다. 예시)graph[0] 에 저장된 값이 1, 2, 3이라면 0번 노드와 1, 2, 3번 노드..