코딩성장스토리

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제는 그래프 탐색 문제이고 DFS, BFS 둘다 이용해서 풀었다. 1.DFS 를 이용한 풀이 #include #include #include using namespace std; int nmSheet[101][101]; bool check[101][101]; int m, n; int cnt=0; void dfs(int a, int b) { if (check[a][b] ==..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이 문제는 DFS와 BFS의 개념을 이용하고 푸는 문제이다. 이에 대한 개념은 자료구조의 그래프 부문에 설명되어 있다. #include #include #include #include #include #define PI 3.1415926535 using namespace std; bool check1[1001] = { 0 }; bool check2[1001] ..

그래프 용어정리 정점(node,vertex) 간선(edge) - 정점간의 관계 경로 .정점 a에서 b로가는 경로 사이클- 시작과 도착이 같은 곳(정점 a에서 다시 a로 돌아오는 경로 단순 경로/단순 사이클 1.경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클 2.특별한 말이 없으면 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말함 방향 있는 그래프 a → b 이면 b→a 는 없다. 방향 없는 그래프(양방향 그래프) a - b 두 정점사이의 방향이 없다. a → b , b→a 두개를 다 나타난다. 루프 간선의 양 끝 점이 같은 경우 a → a 가중치 간선에 가중치가 있는 경우 ex) a에서 b로 이동하는 거리, 이동하는데 필요한 시간 등등 ... 차수 정점과 연결되어 있는 간선..