2606번

https://www.acmicpc.net/problem/2606

2606번: 바이러스

이번에는 BFS와 DFS 중에 선택하여 푸는 문제를 풀어보았다. 나는 우선 BFS에 대해 공부하기 위해서 BFS로 풀었다. 그리고 문제를 생각했을 때 DFS보다는 BFS가 접합하다고 생각했다. 왜냐하면 시작 노드와 근접한 모든 노드를 찾는 것이기 때문에 DFS로 하나의 노드에 대해서 계속 찾아갔다가 돌아오는 방식은 오래걸릴 것 같아서이다.

또한 잘못하여 노드의 깊이가 너무 깊을 경우 시간 초과가 발생할 것이라고 생각했기 때문이다.

그래서 다른 BFS구현과 마찬가지로 구현을 했고, 여기서 바이러스에 감염된 컴퓨터수는 방문여부 리스트를 활용하여 계산하였다.

처음에 값이 이상하게 나와서 문제를 다시 읽어보는 일도 있었다.

이 문제에서 주의할 것은 시작노드는 포함하지 않는다는 것이다.

그렇게 방문여부를 판단하면서 인접노드들을 방문하고 방문처리 후 큐에넣는 식으로 처리한다.

 

정답코드는 아래와 같다.

package backjoon.b2606;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class b2606 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node = Integer.parseInt(br.readLine());
        int edge = Integer.parseInt(br.readLine());
        StringTokenizer st;
        Graph g = new Graph(node);
        for(int i=0; i<edge; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.addEdge(u,v);
        }
        g.bfs(1);
        int count = 0;
        for(boolean i : g.visit){
            if(i){
                count++;
            }
        }
        System.out.println(count-1);
    }
}
class Graph{
    int node;
    LinkedList<Integer>[] adj;
    boolean[] visit;
    Queue<Integer> queue;
    public  Graph(int node){
        this.node=node;
        adj=new LinkedList[node+1];
        visit=new boolean[node+1];
        for(int i=0; i<=node; i++){
            adj[i]=new LinkedList<>();
        }
        queue=new LinkedList<>();
    }
    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    public void bfs(int R){
        visit[R]=true;
        queue.add(R);
        while (!queue.isEmpty()){
            int tmp=queue.poll();
            for(int i : adj[tmp]){
                if(!visit[i]){
                    visit[i]=true;
                    queue.add(i);
                }
            }

        }
    }
}

 

 

 

아래의 글에 다른 문제로 BFS에 대한 설명을 그림으로 해두었다. 읽어보면 좋을 것 같다.

https://parkjunbackend.tistory.com/50

b24444번