Graph 1. 그래프 1) 그래프란? - 노드들의 연결관계를 표시하는 엣지의 집합으로 포함되는 자료구조이다. - 트리는 노드와 엣지의 연결관계가 있고, 한 노드에서 다른 노드로 갈 때의 경로가 유일해야한다. 그래프는 그보다 더 상위의 개념으로 연결관계만 있으면 된다. vertex는 노드와 같은 개념이다. - n은 대부분 입력되는 데이터의 개수를 의미한다. - 방향성을 가지냐는 것도 중요하다. 이를테면 a, b가 입력됐을 때 a에서 b로 갈 수 있는지, b에서 a로 갈 수 있는지, 양방향으로 모두 갈 수 있는지를 알아야지 그래프의 모양을 그릴 수 있다. undirect 그래프는 양방향이다. 일반적으로 undirect는 링크라는 표현을 direct는 엣지라는 표현을 많이 사용한다. - direct 그래프는..

Binary Search Tree 1. Tree 1) Graph와 Tree (1) Graph - 노드간의 연결관계가 표현된 것 - Tree는 여기에 해당된다. 따라서 트리는 그래프의 특성에 더하여 추가적인 특징을 가지고 있다. (2) Tree - 한 노드에서 시작해 다른 노드로 도달하는 모든 연결이 유일하게 있어야한다. (3) Binary tree - 이는 트리의 특성과 더하여 추가적인 특성이 존재한다. - 자식이 최대 2개까지 오는 트리 - 리프를 제외한 모든 노드가 풀로 가지고 있는 경우 complete binary tree라고 한다. 이때 2의 높이 승 -1개만큼 노드의 개수를 가진다. 2) Tree의 특징 (1) Level - Root node는 0 Level - 아래로 한 단계 내려갈수록 Lev..

문제 정의 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착..

문제 정의 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 예제 입력 1 6 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 2 예제 입력 2 6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3 예제 출력 1 1 접근 방법 1. DFS를 통해 하나의 노드를 통해 연결되어있는 모든 노드를 탐색 및 방문처리하고 하나..

문제 정의 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된..

DFS - 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. - 스택 자료구조(혹은 재귀 함수)를 이용한다. DFS의 동작과정 0. 그래프를 준비한다. (해당 강의에서는 번호가 낮은 인접 노드 순으로 방문하는 기준을 세움) 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없드면 스택에서 최상단 노드를 꺼낸다. 3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 코드 - 위의 그래프를 다음과 같이 코드로 작성할 수 있다. graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3..