-

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 백준 DFS 연습 문제이다. 주어진 밭의 정보에서 배추들의 '군' 개수를 dfs 탐색으로 찾는 문제였다. 각 테스트 케이스마다 밭에 ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 DFS 연습 문제이다. 최근 문제풀면서 DFS에 대한 응용력이 부족한것같아 풀어보았다. 원리와 성격을 알지만 응용을 잘 할 수 있게 지속적으로 연습하자. 이 문제는 각 정점에서 다른 정점으로 갈 수 있는 경로가 있다면 1, 아니면 0을 N x N 행렬에 저장해 출력하라는 문제다. 모든 정점 쌍에 대해 dfs 탐색을 하면 시간 초과가 뜨지만, 한 정점에서 갈 수 있는 모든 점들을 찾으면 그 점들에 갈 수 있는 경로가 있다는 뜻이므로 실..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net BFS와 DFS 완전탐색에 대한 그래프 문제다. BFS/DFS에 대한 개념을 잡게해주는 문제였다. 깊이우선 탐색과 너비우선 탐색. 각각의 성격에 대해 통찰을 얻을 수 있었다. #include #include #include #include #define maxVirtex 1000+1 u..