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

키베이루's diary

[C++] 백준 2667번 단지번호붙이기

1) 문제설명 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2) 아이디어 처음 좌표는 0,0으로 잡고 가로를 X 세로를 Y로 잡았다. 배열을 순환하다가 값이 1일 경우 DFS함수를 호출하여 카운트를 하나 증가시키고 값을 0으로 초기화시킨다. 이후 다시 X의 좌표와 Y의 좌표에 각각 +1, -1 씩 더하여 DFS를 재귀적으로 호출하였다. 이때 X, Y의 좌표가 1이 아닐 경우 아무것도 하지 않고 return 하기 때문에 1이 연속적으로 붙어있는..
알고리즘/BFS, DFS 2022. 6. 8. 12:30
[C++] 백준 24445번 알고리즘 수업 - 너비 우선 탐색 2

1) 문제설명 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 2) 아이디어 문제에서 내림차순으로 방문한다고 하였으므로 노드들을 입력받은 후 내림차순으로 정렬한다. BFS대로 노드를 순회하며 방문한 곳을 체크하고 그 노드를 몇 번째 방문했는지 알기 위해 카운트를 세고 저장한다. 이후 카운트를 저장한 배열을 순서대로 출력한다. ※ 정점을 방문한 순서가 아닌 정점이 몇 번째로..
알고리즘/BFS, DFS 2022. 6. 7. 11:31
[C++] 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

1) 문제설명 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 2) 아이디어 문제에서 오름차순으로 방문한다고 하였으므로 노드들을 입력받은 후 오름차순으로 정렬한다. BFS대로 노드를 순회하며 방문한 곳을 체크하고 그 노드를 몇 번째 방문했는지 알기 위해 카운트를 세고 저장한다. 이후 카운트를 저장한 배열을 순서대로 출력한다. 3) 코드 #include #include #..
알고리즘/BFS, DFS 2022. 6. 7. 11:24
[C++] 백준 24480번 알고리즘 수업 - 깊이 우선 탐색 2

1) 문제설명 https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 2) 아이디어 문제에서 내림차순으로 방문한다고 하였으므로 노드들을 입력받은 후 내림차순으로 정렬한다. DFS대로 노드를 순회하며 방문한 곳을 체크하고 새로운 배열에 저장한다. 이후 방문한 순서대로 노드를 출력한다. 3) 코드 #include #include #include #include #include #in..
알고리즘/BFS, DFS 2022. 6. 7. 03:39
[C++] 백준 24479번 알고리즘 수업 - 깊이 우선 탐색 1

1) 문제설명 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 2) 아이디어 문제에서 오름차순으로 방문한다고 하였으므로 노드들을 입력받은 후 오름차순으로 정렬한다. DFS대로 노드를 순회하며 방문한 곳을 체크하고 새로운 배열에 저장한다. 이후 방문한 순서대로 노드를 출력한다. 3) 코드 #include #include #include #include #include #in..
알고리즘/BFS, DFS 2022. 6. 7. 02:48
[C++] 백준 2606번 바이러스

1) 문제설명 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2) 아이디어 그래프를 만들어 BFS로 탐색하고 노드들을 방문할 때마다 카운트를 세서 방문한 총노드를 구한다. 3) 코드 #include #include using namespace std; int graph[101][101]={0,}; int c[101]; queue q; int cnt = 0; void bfs(int start, int n) { queue q; q.push(start)..
알고리즘/BFS, DFS 2022. 6. 5. 01:27
Prev 1 2 3 Next