[C++] 백준 2606 - 바이러스

메르센고수·2023년 12월 27일

BFS Graph cpp 자료구조

Baekjoon

목록 보기

38/48

문제 - 바이러스 (Silver3)

[백준 2606] https://www.acmicpc.net/problem/2606

풀이 전략

이 문제는 깊이우선탐색(DFS)와 너비우선탐색(BFS) 둘 다 풀 수 있다. 하지만, 경로의 경우의 수에 따라 DFS는 시간복잡도가 매우 커질 수 있으므로 BFS로 풀었다.

이번 학기 박희진 교수님의 <알고리즘및문제해결기법> 수업을 듣고 Adjacency list와 Adjacency Matrix로 접근하는 방식을 배웠고, 시험기간에 BFS와 DFS의 Pseudo code를 열나게 외웠던 기억이 있어서 BFS와 관련된 문제를 풀어 보았다.

Adjacency List

이런 식으로 방향이 있는 그래프의 경우 정점에서 도달할 수 있는 정점을 Linked-list 처럼 연결해주는 방법이다. 이 경우, 시작 정점을 Queue에 push하고 push했던 정점을 pop하면서 pop한 정점이 도달할 수 있는 정점(예를들어 r의 경우 s와 v)을 Queue에 push하는 과정을 Queue가 비어 있을 때까지 반복하는 과정으로 문제를 해결한다.

Adjacency Matrix

Adjacency List와 동일하지만 표현 방식이 다르다. Adjacency Matrix의 경우, 행의 좌표가 시작 정점이 되고, 열의 좌표가 도착 정점이 된다. 예를 들어, 1행 4열 (1,4)의 경우 1번 정점에서 시작해서 4번 정점에 도착하는 파란색 선을 의미한다. 특징이 있다면, 방향이 있는 그래프와 달리 방향이 없는 그래프의 경우 행렬이 대칭행렬의 성질을 지니게 되기 때문에 아래 그림처럼 대각성분의 아래 또는 위쪽을 계산하지 않아도 되기 때문에 계산 시간을 단축할 수 있다.

다시 문제로 돌아와서, 문제에 대한 해석을 해보면 <그림1>처럼 입력받은 값들로 그래프를 그렸을 때 만약 1번 컴퓨터가 바이러스에 감염되었다면 BFS 탐색을 통해 도달할 수 있는 2,3,5,6번 컴퓨터가 바이러스에 감염될 수 있기 때문에 4대를 결과로 출력하면 되는 문제이다.

수도 코드

이건 시험기간에 암기했던 pseudo code이다. 알고리즘 책에 나와있기 때문에 아마 거의 대부분 아는 코드일 것이다.

소스 코드

c++ - BFS

/*문제 : https://www.acmicpc.net/problem/2606
  알고리즘 : Graph, BFS, DFS
  티어 : Silver3
*/

#include <iostream>
#include <queue>
#define MAX 101 // 100 이하의 양의 정수
using namespace std;

int count=0;
int N, Pair;
queue <int> Q;
int G[MAX][MAX];
bool visited[MAX]={0,};

void BFS(int s){
    Q.push(s);
    visited[s]=true;

    while(!Q.empty()){
        s=Q.front();
        Q.pop();

        for(int i=1;i<=N;i++){
            if(G[s][i]==1 && visited[i]==0){ 
            // 경로가 있는데 방문하지 않았을 경우
                Q.push(i);
                visited[i]=true;
                count++;
            }
        }
    }   
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>Pair;

    for(int i=0;i<Pair;i++){
        int start, end;
        cin>>start>>end;
        G[start][end]=1;
        G[end][start]=1;
    }
    BFS(1);
    cout<<count<<'\n';
    return 0;
}

원래는 C++로 BFS를 이용하여 풀었는데, 최근에 친구들과 알고리즘 스터디를 하면서 이 문제를 또 풀게 되어서 이번엔 Python으로 DFS를 이용하여 풀어보았다.

python

# Question: BJ 2606 (https://www.acmicpc.net/problem/2606)
# Rank : Silver 3
# Algorithm : DFS/BFS

N=int(input())
M=int(input())

G=[[] for _ in range(N+1)]
visited=[False]*(N+1)
cnt=-1

for i in range(M):
    s,e=map(int, input().split())
    G[s].append(e);
    G[e].append(s);

def DFS(v):
    visited[v]=True
    global cnt  # global 선언을 하지 않으면 -1로 선언한 cnt를 못읽음
    cnt+=1
    # 모든 vertex를 방문하면서 방문하지 않았으면 DFS 실행
    for i in G[v]:
        if not visited[i]:
            DFS(i)

DFS(1)
print(cnt)

2024.01.10 C++ DFS 추가

c++

#include <iostream>
#include <vector>
#define MAX 105
using namespace std;

int N,M,cnt=0;
vector<int> G[MAX];
bool visited[MAX];

void DFS(int v){
    visited[v]=true;
    for(int t=0;t<G[v].size();t++){
        int k=G[v][t];
        if(!visited[k]){
            cnt++;
            DFS(k);
        }
    }
    return;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>M;

    for(int i=0;i<M;i++){
        int start, end;
        cin>>start>>end;
        G[start].push_back(end);
        G[end].push_back(start);
    }
    DFS(1);
    cout<<cnt<<'\n';
    return 0;    
}