[백준 2606] 바이러스

백준 2606 바이러스

이 문제는 (매우..?) 쉬운 문제이다.

알고리즘 분류에는 플로이드 와샬로 되어있는데 이건 단순히 DFS로 풀린다.

입력 받는 데이터를 이용해 인접리스트를 만들고 컴퓨터 1번에서 DFS를 한 번 돌리면 답이 나온다.

#include<cstdio>
#include<vector>
 
using namespace std;
 
vector<vector<int>> map;
bool visit[101] = { false };
int computer_num, ans = 0;
 
void dfs(int x)
{
    ans++;
    visit[x] = true;
 
    for (int k = 0; k < map[x].size(); k++)
    {
        if (!visit[map[x][k]])dfs(map[x][k]);
    }
    return;
}
 
int main()
{
    int n, from, to;
    scanf("%d %d", &computer_num, &n);
    map.resize(computer_num + 1);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &from, &to);
        map[from].push_back(to);
        map[to].push_back(from);
    }
 
    dfs(1);
 
    printf("%d", ans - 1);
    return 0;
}r

어떤 God 분이 visit도 vector로 바꿔라 해서 vector로 한번 바꿔보았다.

#include<cstdio>
#include<vector>
 
using namespace std;
 
vector<vector<int>> map;
vector<bool> visit;
int computer_num, ans = 0;
 
void dfs(int x)
{
    ans++;
    visit[x] = true;
 
    for (int k = 0; k < map[x].size(); k++)
    {
        if (!visit[map[x][k]])dfs(map[x][k]);
    }
    return;
}
 
int main()
{
    int n, from, to;
    scanf("%d %d", &computer_num, &n);
    visit.resize(computer_num + 1);
    map.resize(computer_num + 1);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &from, &to);
        map[from].push_back(to);
        map[to].push_back(from);
    }
 
    dfs(1);
 
    printf("%d", ans - 1);
    return 0;
}

+ 다른 풀이

 벡터 사용하지 않고 이차원 배열로 사용한 풀이

#include<cstdio>
 
int map[101][101] = { 0 };
int visit[101] = { 0 };
int computer_num, ans = 0;
 
void dfs(int n)
{
    ans++;
    visit[n] = 1;
    for (int i = 1; i <= computer_num; i++)
    {
        if (map[n][i] && !visit[i])dfs(i);
    }
}
 
int main()
{
    int n;
    int x, y;
    scanf("%d %d", &computer_num, &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        map[x][y] = map[y][x] = 1;
    }
 
    dfs(1);
 
    printf("%d", ans - 1);
 
    return 0;
}
 

플로이드 와샬을 이용한 풀이(정해)

#include<cstdio>
 
int map[101][101] = { 0 };
int computer_num, ans = 0;
 
int main()
{
    int n;
    int x, y;
    scanf("%d %d", &computer_num, &n);
    for (int i = 1; i <= computer_num; i++)
    {
        for (int j = 1; j <= computer_num; j++)
        {
            map[i][j] = 10000;
        }
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        map[x][y] = map[y][x] = 1;
    }
 
    for (int k = 1; k <= computer_num; k++)
    {
        for (int i = 1; i <= computer_num; i++)
        {
            for (int j = 1; j <= computer_num; j++)
            {
                if (map[i][j] > map[i][k] + map[k][j])map[i][j] = map[i][k] + map[k][j];
            }
        }
    }
 
    for (int i = 2; i <= computer_num; i++)
    {
        ans += map[1][i] != 10000;
    }
 
    printf("%d", ans);
 
    return 0;
}