[BOJ] 2606번 바이러스

개요

그래프 경로를 탐색하는 문제

문제링크

코드

import java.io.*;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Baekjoon2606 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int comNum = Integer.parseInt(br.readLine());   //컴퓨터의 갯수
        int netNum = Integer.parseInt(br.readLine());   //연결된 경로의 갯수

        LinkedList<Integer>[] computer = new LinkedList[comNum];    //컴퓨터의 연결경로 저장
        boolean[] isVisited = new boolean[comNum];  //컴퓨터를 방문했는지 확인하는 배열
        for (int i = 0; i < computer.length; i++) 
            computer[i] = new LinkedList<>();

        int index, target;
        for (int i = 0; i < netNum; i++) {
            st = new StringTokenizer(br.readLine());
            index = Integer.parseInt(st.nextToken())-1;
            target = Integer.parseInt(st.nextToken())-1;

            computer[index].add(target);
            computer[target].add(index);    //양뱡향 그래프이므로 양쪽에 모두 경로를 추가해줌
        }

        Stack<Integer> s = new Stack();
        s.push(0);
        isVisited[0] = true;
        int popItem, temp, count = 0;
        Iterator it;
        while(!s.isEmpty()) {   //스택을 이용한 DFS 탐색
            popItem = s.pop();
            it = computer[popItem].iterator();
            while(it.hasNext()) {
                temp = (int)it.next();
                if(!isVisited[temp]) {
                    s.push(temp);
                    isVisited[temp] = true;
                    count++;    //감염된 컴퓨터 카운트
                }
            }
        }
        
        bw.write(count+"\n");
        bw.flush();
    }
}

해결 과정

2차원배열에서 미로탐색방식의 탐색은 많이 해보았지만 그래프 경로의 탐색은 거의 안 풀어보았기에 선택한 문제

연결리스트의 배열을 선언해서 그래프의 정점마다 경로를 연결리스트에 저장해 탐색하는데 사용하였다.

그리고 연결되어있는 모든 정점만 찾으면 되기 때문에 BFS, DFS 중에 아무거나 선택해서 사용해도 되었는데 나는 DFS를 선택해 풀이하였다.

결과