목록알고리즘/BFS, DFS (22)

키베이루's diary

[C++] 백준 2583번 영역 구하기

1) 문제설명 2) 아이디어 처음 M,N 행렬을 0으로 초기화 한 뒤 입력받은 위치(X1 X2 ~ Y1 Y2)는 1로 변경해 주었다. 이후 BFS를 실행하여 영역크기는 각각 vector에 저장하여 오름차순으로 출력하였고 영역의 개수는 따로 카운트 하였다. 3) 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include using namespace std; queue q; int arr[101][101]; int range[101][101]; int result = 0; int cnt = 0; int n, m, k; int x1, y11, x2, y2; voi..
알고리즘/BFS, DFS 2023. 1. 13. 10:39
[C++] 백준 1707번 이분 그래프

1) 문제설명 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 2) 아이디어 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지의 색으로 칠할 수 있는 그래프를 말한다. 이분 그래프를 구현하기 위해서 bfs를 사용하고 bfs로 정점들을 방문하되 번갈아 가면서 색을 칠해준다. visited배열에 red는 1로 blue는 2로 인접한 정점을 방문하면서 저장하였다. 이후 정점들을 차례로 방문하면서 인접한 정점이 색이 같다면 ..
알고리즘/BFS, DFS 2022. 7. 16. 17:13
[C++] 백준 4963번 섬의 개수

1) 문제설명 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2) 아이디어 BFS 혹은 DFS를 이용해 순회하면서 섬의 개수를 찾는 문제이다. BFS를 사용하여 순회하고 BFS가 종료되면 카운트를 세주는 방식으로 구현하였다. 여러 번의 테스트 케이스를 사용해야 하기 때문에 전역 변수로 선언된 큐와 배열을 초기화하는 것을 잊지 말자. 3) 코드 #include #include #include #include #include #include..
알고리즘/BFS, DFS 2022. 7. 13. 14:16
[C++] 백준 15650번 N과 M (2)

1) 문제설명 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2) 아이디어 기존 n과 m (1)에서 풀었던 백트래킹을 이용한다. 단 이번에는 중복을 허용하지 않기 때문에 dfs를 돌 때 1부터 순회하는 것이 아닌 그다음수부터 순회하면 중복이 사라진다 ex ) 순회하다가 (2 1 x) , (2 2 x)을 순회하는 것이 아닌 2의 다음수인 (2 3 x) 순으로 순회한다. 3) 코드 #include #include #include #include..
알고리즘/BFS, DFS 2022. 6. 20. 02:30
[C++] 백준 15649번 N과 M (1)

1) 문제설명 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2) 아이디어 DFS를 사용하여 백트래킹으로 구현한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int visited[11]; int arr[11]; int m, n; void dfs(int k) { if (k == m) { for (int i =..
알고리즘/BFS, DFS 2022. 6. 19. 00:49
[C++] 백준 2468번 안전 영역

1) 문제설명 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2) 아이디어 비가 오는 높이를 0~100까지 전부 반복문으로 돌리면서 BFS를 실행한다. 입력받은 영역이 비가오는 높이보다 크다면 1로 작으면 0으로 설정해주어서 단순화시킨다. 영역 배열을 하나 더 선언해 계속 입력받은 배열로 다시 초기화시켜주는 것이 중요하다. 3) 코드 #include #include #include #include #include #include #include #i..
알고리즘/BFS, DFS 2022. 6. 17. 14:33
[C++] 백준 11724번 연결 요소의 개수

1) 문제설명 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 2) 아이디어 BFS를 사용하여 정점의 개수만큼 BFS를 실행하고 방문하지 않은 정점이 들어올 때마다 카운트를 증가시켜서 연결 요소의 개수를 구하였다. 3) 코드 #include #include #include #include #include #include #include #include using namespace s..
알고리즘/BFS, DFS 2022. 6. 16. 16:33
[C++] 백준 13023번 ABCDE

1) 문제설명 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2) 아이디어 정점들을 입력하고 모든 정점에서 DFS를 따로따로 돌려주어서 DFS를 실행한 횟수가 4번 이상이면 친구의 친구가 4번있다는 뜻이다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int visited[2001]={0,}; vector v[2001]; int flag = 0; int maxt = 0; void dfs(int x, int cnt) {..
알고리즘/BFS, DFS 2022. 6. 14. 13:28
Prev 1 2 3 Next