https://www.acmicpc.net/problem/2606
코드 설명
DFS,BFS 모두 이용해서 간단하게 풀어보았다.
map에 시작과 끝을 전부 1로 체크하고,
DFS의 경우 문제에서 1번 컴퓨터만 물어보았으므로 main에서 DFS한번 실행한다.
cycle 방지위해 visit배열로 막아준다.
코드 (DFS 풀이)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int map[101][101];
bool visited[101];
int cnt;
void dfs(int level, int now) {
visited[now] = true;
if (level == N) return;
for (int i = 0; i < N; i++) {
if (map[now][i] == 1 && !visited[i]) {
cnt++;
dfs(level + 1, i);
}
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
map[a-1][b-1] = 1;
map[b - 1][a - 1] = 1;
}
dfs(0, 0);
cout << cnt;
return 0;
}
코드 (BFS풀이)
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int> graph[101];
bool visited[101];
int cnt = 0;
void bfs(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int a = q.front();
q.pop();
for (int i = 0; i < graph[a].size(); i++) {
int b = graph[a][i];
if (!visited[b]) {
q.push(b);
visited[b] = true;
cnt++;
}
}
}
cout << cnt;
}
int main()
{
int n;//computer수
int k;//연결 쌍 수
cin >> n >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
bfs(1);
return 0;
}
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] 촌수계산 (0) | 2021.05.04 |
---|---|
[백준] 단지번호붙이기 (0) | 2021.05.02 |
[백준] 문자열 (0) | 2021.05.02 |
[백준] 섬의 개수 (0) | 2021.04.28 |
[백준] 괄호 (0) | 2021.04.28 |