Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 백준 알고리즘
- 백준 15651
- 백준알고리즘
- backtracking
- 백준 1697
- 15651c++
- Programmers
- fill함수
- 2370 c++
- MySQL
- 위상정렬
- 삼성 SW역량 테스트
- 에라토스테네스의 체
- 주린이
- 삼성SW 역량 테스트 기출문제
- 삼성 SW 역량 테스트 기출 문제
- 프로그래머스
- 백준 2370
- 브루트포스
- 주식 용어
- 용어 정리
- 15651
- DFS
- 주식 용어 정리
- 시장 선거 포스터 c++
- DP
- 백준
- BFS
- C++
- 백트레킹
Archives
- Today
- Total
빠켱이
백준 2606번 바이러스[C++] 본문
2606은 1260번과 거의 흡사하게 bfs dfs의 기초 문제라고 볼 수 있습니다.
저는 2606번을 dfs를 사용하여 풀이하였습니다.
1260번을 풀이하셨다면 별다른 설명이 필요 없을 것 같은 문제입니다.
혹시 1260번을 풀지 않으셨다면 1260번을 먼저 푸는것을 추천드립니다. 1260 >> https://bbakyunge.tistory.com/10
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> v;
vector<bool> visit;
int result = 0;
void dfs(int a);
int main() {
int n, m, tmp1, tmp2;
scanf("%d %d", &n, &m);
v.resize(n + 1);
visit.resize(n + 1);
for (int i = 0; i < m; i++) {
scanf("%d %d", &tmp1, &tmp2);
v[tmp1].push_back(tmp2);
v[tmp2].push_back(tmp1);
}
dfs(1);
printf("%d", result - 1);
return 0;
}
void dfs(int a) {
result++;
visit[a] = true;
for (int i = 0; i < v[a].size(); i++) {
if (!visit[v[a][i]]) {
dfs(v[a][i]);
}
}
return;
}
main문에서는 주어진 input값에 따라 그래프 연결상태를 완성시켰습니다. 기존 저의 1260번 풀이와 다른 점이라면 기존에는 배열을 사용하여 정점 번호를 index값을 사용해 연결된 곳은 1 연결되지 않은 곳은 0을 사용하였지만 해당 문제에서는 vector를 사용하여 해당 정점에 해당되는 index에 연결된 정점의 값을 push_back 해주었습니다.
이후에는 연결된 점들을 찾을 때마다 result++을 해주어 프로그램을 완성하였습니다.
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
백준 2178번 미로탐색[C++] (0) | 2020.09.12 |
---|---|
백준 2667번 단지번호붙이기[C++] (0) | 2020.09.09 |
백준 1904번 01타일[C++] (0) | 2020.09.01 |
백준 1260번 DFS와 BFS[C++] (0) | 2020.08.29 |
백준 14888번 연산자 끼워넣기[C++] - 삼성 SW 역량 테스트 기출문제 (0) | 2020.08.19 |
Comments