[BOJ] 2606. 바이러스

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

2606번: 바이러스

---

접근 방법

stack을 이용한 DFS 방식으로 풀었다. DFS에 대한 개념을 복기하기 좋은 기초 문제였다.

(1) 시작 노드 stack 삽입 & 방문 처리

(2) 탐색 노스 stack 삽입

(3) stack이 빌 때까지 최근 삽입한 노드부터 조회 & 인접 노드 존재 false

(4) visited를 통해 방문 X 인접 노드 존재하면, stack 삽입 & 방문 처리 & 인접 노드 존재 true & Break

(5) 방문 X 인접 노드 존재하지 않으면, stack에서 현재 노드를 삭제

 

소스 코드

 import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
		int tc = Integer.valueOf(br.readLine());
		int c = 0;
		
		ArrayList<ArrayList<Integer>> g = new ArrayList<>();
		boolean[] visited = new boolean[n];
		
		for(int i=0; i<n; i++) {
			ArrayList<Integer> v = new ArrayList<>();
			g.add(v);
			visited[i] = false;
		}
		
		for(int i=0; i<tc; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int nn = Integer.valueOf(st.nextToken());
			int mm = Integer.valueOf(st.nextToken());
			
			g.get(nn-1).add(mm-1);
			g.get(mm-1).add(nn-1);	
		}
        
		Stack<Integer> s = new Stack<>();
		s.push(1-1);
		
		visited[1-1] = true;
		
		while(!s.isEmpty()) {
			int ns = s.peek();
			boolean hasNode = false;
			
			for(int i: g.get(ns)) {
				if (!visited[i]) {
					s.push(i);
					visited[i] = true;
					hasNode = true;
					c += 1;
					break;
				}
			}
			if(hasNode == false)
		}
		
		System.out.println(c);
	}
}