그래프
-
그래프 간선의 분류 간단 정리컴퓨터 과학/자료구조와 알고리즘 2021. 9. 14. 22:41
참고 https://rebro.kr/71 https://hy38.github.io/about-edges-in-graph https://bowbowbow.tistory.com/1 https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm 설명 아래와 같은 그래프가 있습니다. 1번 정점부터 깊이 우선으로 탐색을 시작하면 다음과 같은 스패닝 트리가 나옵니다. 스패닝 트리를 연결하고 있는 간선을 스패닝 트리 간선이라고 합니다. 스패닝 트리에는 순환이 없습니다. 스패닝 트리는 이미 방문한 노드는 방문하지 않기 때문에 (5, 1), (6, 4), (6, 3), (1, 7) 간선은 스패닝 트리에 포함되지 않습니다. 여기에서 순방향 간선, 역..
-
[백준][2667번] 단지번호 붙이기알고리즘/백준 2021. 8. 9. 20:29
문제 링크 풀이 아직 방문하지 않은 집을 방문해 인덱스를 큐에 넣고, 인접 노드를 검사해 방문한 적 없는 집이라면 해당 인덱스를 큐에 넣는 걸 반복합니다. 코드 #include #include using namespace std; int main() { int N; scanf("%d", &N); char map[25][25] = {}; bool flag[25][25] = {}; int row_dir[] = {0, 1, 0, -1}; int col_dir[] = {1, 0, -1, 0}; for (int i = 0; i < N; ++i) scanf("%s", map[i]); priority_queue pq; int count = 0; for (int i = 0; i < N; ++i) { int answer..
-
[백준] 결혼식(5567)알고리즘/백준 2019. 8. 14. 16:05
문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai Colored by Color Scripter