[백준 알고리즘] 2606 바이러스 (21.05.02)

오늘은 원래 구현 이었으나

....

 

 

 

굳이 스터디로 안 해도 될 것 같아

BFS/DFS !!!!!!!!!!!!!!

 

 

오랜만에 하는 것이라 잘 기억이 안나

책을 더듬 더듬 찾아보며 했다 ...........

 

 

---

 

 

 

그래서 오늘의 문제는

 

 

 

 

백준 2606번 바이러스

 

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

 

문제 사이트 : www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

 

---

여기서 핵심 포인트!!!

 

는 별거 없다

 

 

 

- 가장 중요한 그래프 구현하기 !!!!!!

 

- BFS 혹은 DFS 탐색 

 

---

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

import java.util.ArrayList;
import java.util.Scanner;

class AdjListGraph {
	private ArrayList<ArrayList<Integer>> adjListGraph;
	private boolean visited[] = new boolean[1000];
	private int count = 0;
	
	public AdjListGraph(int size) {
		this.adjListGraph = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < size + 1; i++) {
			adjListGraph.add(new ArrayList<Integer>());
		}
	}

	public ArrayList<ArrayList<Integer>> getGraph() {
		return this.adjListGraph;
	}

	public ArrayList<Integer> getNode(int i) {
		return this.adjListGraph.get(i);
	}

	public int getNodeSize(int i) {
		return this.adjListGraph.get(i).size();
	}

	public void put(int x, int y) {
		adjListGraph.get(x).add(y);
		adjListGraph.get(y).add(x);
	}

	public void resetVisited() {
		for (int i = 0; i < 1000; i++) {
			visited[i] = false;
		}
	}

	public void DFS(int v) {
		visited[v] = true;
	    for (int i=0; i <adjListGraph.get(v).size(); i++) {
	    	int y = adjListGraph.get(v).get(i);
	        if (visited[y] == false){
	        	DFS(y);
	        	count++;
	        }
	    }
	}
	
	public int getCount() {
		return count;
	}

}

public class Virus {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int count, num;
		
		Scanner sc = new Scanner(System.in);
		count = sc.nextInt();
		num = sc.nextInt();
		
		AdjListGraph list = new AdjListGraph(count);
		
		for(int i = 0; i < num; i++) {
			int first, end;
			first = sc.nextInt();
			end = sc.nextInt();
			list.put(first, end);
		}
		
		list.DFS(1);
		
		System.out.println(list.getCount());
	}

}

 

어떻게 풀었는 지 말해보자면...

 

• 인접 리스트 그래프 생성

---

사실 꼭 인접 리스트가 아니어도 되지만,

테스트할 그래프가 작아서 인접 리스트로 해주었다!!!

 

다른 것으로 해도 무방!!

 

---

 

 

• DFS 구현해서 실행시키기
• 이때, 원하는 건 1에 연결된 개수니까 "DFS(1)" 만 해준다는 것!

 

 

 

 

 

---

백준 알고리즘

 

채점 결과!!!

 

 

 

다행히 맞았습니다!!

 

백준 알고리즘 2606 채점 결과

 

 

 

 

 

 

 

 

---

 

스터디하면서 나온 더 좋은 방법들

• 인접 행렬 사용 시 가중치 대신 bool 사용
• map 사용