- BOJ - 바이러스 (2606번)2022년 09월 03일
- 학페
- 작성자
- 2022.09.03.오후07:36
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
DFS를 사용하는 문제였습니다.
DFS와 BFS 정리하는 겸 해결해봤습니다.
재귀함수를 사용한 기본적인 틀은 동일합니다만, 하나 추가적으로 생각해줘야 할 부분이 있습니다.
이 문제는 컴퓨터가 양방향으로 연결되어 있다고 보고 해결해야 하는데요, 이 부분만 코드로 추가해주면 어렵지 않게 해결할 수 있습니다.
#include <iostream> #include <string> #include <vector> #include <cmath> #include <algorithm> #include <utility> #include <stack> #include <queue> #include <deque> #include <utility> #define MIN 0 #define MAX 10000000 using namespace std; typedef unsigned long long int ll; vector<int> graph[101]; bool infected[101] = { false, }; void dfs(int x); int cnt = 0; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //DFS 사용 int com; // 컴퓨터 수 int pair; // 연결된 컴퓨터 쌍의 수 cin >> com >> pair; for (int i = 1; i <= pair; i++) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } infected[1] = true; dfs(1); cout << cnt << '\n'; } void dfs(int x) { infected[x] = true; // 감염됨 for (int i = 0; i < graph[x].size(); i++) // x번 컴퓨터와 연결된 수 만큼 반복 { int temp = graph[x][i]; // x번 컴퓨터와 연결된 컴퓨터의 번호가 들어감 if (!infected[temp]) {// x번 컴퓨터와 연결되었는데, 감염 표시가 안되었다면 dfs(temp); cnt++; } // 감염됐음을 표시하고, graph[temp]와 연결된 //또 다른 그래프가 있는지 확인하기 위해 재귀 } }
graph[a].push_back(b);
graph[b].push_back(a);이 부분이 양방향을 구현하는 부분이었습니다.
다음은 BFS를 풀어봐야겠네요. 감사합니다.
'Baekjoon Online Judge > C++' 카테고리의 다른 글
BOJ - 토마토 (7576번) (0) 2022.09.08 BOJ - 미로 탐색 (2178번) (0) 2022.09.04 BOJ - 5의 수난 (23037번) C++ (0) 2022.07.13 BOJ - 중복된 숫자 (15719번) C++ (0) 2022.07.11 BOJ - 연속합 (1912번) C++ (0) 2022.06.28 다음글이전글이전 글이 없습니다.댓글
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)