목록DFS (6)

안녕 세상아,

[c++/백준] 4963 섬의 개수 (bfs)

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 전에는 4방 탐색을 풀었다면 이번에는 8방 탐색문제이다. 대각선까지 신경써줘야되기 때문에 좌표를 조금 더 생각해주면 된다. 좌표가 주어지는 것이 아닌 배열이 전체가 주어지기 때문에 배열 전체를 입력 받으면 된다. #include #include using namespace std; int map[51][51]; bool isVisited[51][51] = { false }; int w, h;..
백준 2023. 6. 15. 15:26
[c++/백준] 1012 유기농 배추

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 일반적인 그래프에 조건이 있는 문제였다. 사실 이런 문제를 처음 풀어봐서 다른 사람 코드를 이해하는 것도 오래 걸렸다. 내가 이해한 자세한 설명은 코드에 적어놨다. #include #include //memset 사용하기 위함 using namespace std; int m, n, k; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; bool isVisited[51..
백준 2023. 6. 12. 21:47
[c++/백준] 11724 연결 요소의 개수

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 연결 요소가 뭔지 몰라서 문제에서 나온 예제를 직접 그려보며 이해했다. 연결 요소의 개수는 간단하게 말해서 각각 서로 연결되지 않은 그래프의 개수이다. dfs를 이용하여 탐색을 하였고, main문에서 일정한 조건으로 반복문을 돌리면서 cnt를 ++해주었다. #include #include using namespace std; int n..
백준 2023. 6. 2. 17:50
[c++/백준] 1260 DFS와 BFS

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 using namespace std; int n, m, v;//정점, 간선, 시작 정점 bool isVisited[1001] = { false };//정점 방문 여부 int map[1001][1001];//인접 행렬 그..
백준 2023. 5. 17. 16:53
[c++/백준] 2606 바이러스

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 내가 처음 접해보는 너비우선탐색, 깊이우선탐색 문제... dfs, bfs 모두 사용해서 해결할 수 있다. #include #include #include using namespace std; vector map[101]; bool visited[101] = { false };//방문 유무 파악 int ans = 0; //재귀를 이용한 dfs int dfs(int n) { for (int i = 0; i..
백준 2023. 5. 8. 13:17
[c++/그래프] DFS (깊이 우선 탐색)

깊이 우선 탐색이란 1. 인접한 정점 중 하나 선택 2. 인접한 정점으로 이동 3. 더이상 이동할 정점이 없을 경우 백트래킹 그래프의 모든 정점을 탐색할 때까지 위의 과정을 반복한다. ​ 시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점 탐색 ​ 보통 재귀, 스택을 이용하여 구현한다. ​ bool isVisited[N] = { }; -> 정점 방문 여부 검사 -> 정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다. #include #include #include #include using namespace std; const int N = 6;//정점 6개 bool gVisited[N] = {};//정점 방문 했는지 확인 void dfs_recursion(const vector..
c++ 개념 2023. 5. 3. 19:11
이전 Prev 1 Next 다음