깊이우선탐색

문제 : 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를 통해 그래프를 탐색하는 순서를 출력하면 되는 간단한 문제이다. 접근 방법 bool visited[1001]; vectorgraph[10001]; 먼저 그래프를 저장할 벡터와 정점의 방문 여부를 저장할 배열이 필요하다. int n,m,v; cin >> n >> m >> v; 문제에서 주어진 변수들을 ..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 어떠한 그래프에 대한 깊이 우선 탐색과 너비 우선 탐색 결과를 각각 출력하면 되는 문제이다. 주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다. 따라서 그래프를 sort함수를 통해 오름차순으로 정렬해줘야 한다. 입력받은 v부터 dfs를 실행한 결과를 출력하고 그래프를 다시 초기 상태로 돌려놔 bfs..

문제 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 깊이 우선 탐색 알고리즘을 사용하면 아주 쉽게 풀 수 있는 문제다. 1번 컴퓨터와 연결된 컴퓨터에 대해서만 탐색을 하면 된다. #include #include using namespace std; bool visited[101]; vector graph[101]; int cnt=0; void dfs(int x){ cnt++; visited[x]=true; for(int i : graph[x])..