BFS

풀이 각 정점에서 연결된 정점들을 번호순으로 처리하기 위해 정렬한다. DFS 함수에서는 현재 정점을 방문하고, 방문했다는 표시를 한 뒤, 현재 정점에 연결된 정점들을 재귀적으로 방문한다. BFS 탐색은 큐를 이용하여 구현한다. DFS 함수와 BFS 함수에서 visited 배열을 공유하지 않도록 주의하면서 구현하면 된다. 코드 #include #include #include #include using namespace std; vector graph[1001]; bool visited[1001]; void dfs(int node) { visited[node] = true; cout m >> v; for(int i = 0; i > a >> b; graph[a]..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고..

[문제 풀이] 영상 참고. www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include using namespace std; int n, m, ans = 0; int field[8][8]; int clone_field[8][8]; int dx[] = { 0,0,-1,1 }; int dy[] = { -1,1,0,0 }; //바이러스를 퍼트림. void bfs(); //a field에 b field를 복사함. void clone_it(int(*a)[8], int(*b)[8]); //세개의 벽을 세움. void make_wall(int cnt); int main() ..

[문제 풀이] 영상 참고 www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include #include #include using namespace std; int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 }; int field[101][101] = { 0, }; int visited[101][101] = { 0, }; int* alti; int n,cnt; queue q; void bfs(int alt, int cnt); int main() { int ans = -1; cin >> n; vector alti; for (int ..

[문제 풀이] 영상 참고 www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include #include #include #include #include using namespace std; int n, m, v; vector a[1001]; bool visited[1001] = { 0, }; stack s; void dfs(int v); void bfs(int v); int main() { ios_base::sync_with_stdio(0); int ltemp, rtemp; cin >> n >> m >> v; while (m--) { cin >> ltemp >> ..

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 드디어 마지막 문제 풀이입니다! 고생 많으셨어요! 이 문제는 탐색 문제입니다. 이번 포스팅에서는 bfs탐색으로 같이 풀어보겠습니다. 이러한 xy좌표가 있는 문제는 풀이 과정이 거의 비슷한 것 같습니다. 깊이 우선 탐색과 너비 우선 탐색은 잘 알고 있다고 가정하고, 어떻게 이 알고리즘들이 적용되었는지 먼저 코드를 보면서 살펴보겠습니다. #include #include using namespace std; int field[5..