글 읽기 - 2606 바이러스 - BFS 로 풀어보았습니다. 틀려서.. 조언 부탁드려요 ㅜ

dodi258 4년 전 0

바이러스 문제를 예전엔 dfs 로 풀었는데

bfs 가 더 직관적인것 같아서 bfs 로 풀자마자 틀렸습니다...ㅜㅜ

왜 틀렸는지 같이 고민해주실 분 있을까요..? ㅜㅜ

읽어주셔서 감사합니다..!

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

public class Main {
    static boolean[] visited; 
    static ArrayList<Integer>[] virus; 
    static int N; 
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st; 
        
        N = Integer.parseInt(in.readLine());
        visited = new boolean[N + 1];
        virus = new ArrayList[N + 1];
        // 바이러스 array 초기화 
        for(int i = 0; i < N + 1; i++) {
            virus[i] = new ArrayList<Integer>();
        }
        int M = Integer.parseInt(in.readLine()); 
        
        while(M --> 0) {
            st = new StringTokenizer(in.readLine()); 
            virus[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
            
        }
        
        //Bfs 
        Queue<Integer> queue = new LinkedList<Integer>(); 
        
        // 첫번째 바이러스를 queue에 삽입 
        queue.add(1); 
        visited[1] = true;
        int virus_cnt = 0; 
        while(! queue.isEmpty()) {
            int num = queue.poll(); 
            // num 번째 바이러스와 연결되어 있는 바이러스만 점검합니다. 
            for(int i = 0; i < virus[num].size(); i++) {
                int virus_num = virus[num].get(i); 
                
                if(! visited[virus_num]) {
                    virus_cnt += 1; 
                    visited[virus_num] = true;
                    queue.add(virus_num); 
                }
            }
        }
        
        System.out.println(virus_cnt); 
        
        
        
    }
    
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2606 바이러스 - BFS 로 풀어보았습니다. 틀려서.. 조언 부탁드려요 ㅜ

dodi258 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말