[백준-자바] N_2606 바이러스

0woy·2024년 10월 27일

BFS DFS Java 백준

코딩테스트

목록 보기

31/40

📜 문제

양방향 연결된 네트워크 쌍이 주어짐
1번 컴퓨터를 시작으로 바이러스에 감염된 컴퓨터 개수 찾기

생각하기

Map을 이용해서 풀면 되겠다고 문제 보고 생각이 들었다.
key에는 컴퓨터 번호, value 값으로 연결된 컴퓨터 list를 넣으면 되고..
key값에 있는 친구들 빼면서 개수 세면 되겠지? 했지만 5%에서 걍 틀리기

양방향인 거 알면서 양방향으로 구현하지 않은 내 잘못이다.
1 2 이렇게 들어오면, 1->2, 2->1 모두 구현해 주고 풀어야한다.

🍳 전체 소스 코드

package DFS_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class N_2606 {
    public static void insert(Map<Integer, List<Integer>> map, int s, int e){
        if(!map.containsKey(s)){
            map.put(s, new ArrayList<>());
        }
        if(!map.containsKey(e)) {
            map.put(e, new ArrayList<>());
        }
            map.get(s).add(e);
            map.get(e).add(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int con = Integer.parseInt(br.readLine());
        boolean [] visited = new boolean[n+1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        while (con > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            insert(map,s,e);
            con--;
        }
        int virus = 0;
        Queue<Integer> que = new ArrayDeque<>();
        que.add(1);
        visited[1]=true;
        while(!que.isEmpty()){
            int key = que.poll();
            if(!map.containsKey(key)){continue;}
            for(int i: map.get(key)){
                if(visited[i]){
                    continue;
                }
                visited[i] = true;
                que.add(i);
                virus++;
            }
        }
        System.out.println(virus);
    }
}

✍ 부분 코드 설명

입력

 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int con = Integer.parseInt(br.readLine());
        boolean [] visited = new boolean[n+1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        
		while (con > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            insert(map,s,e);
            con--;
        }
        ...

n : 전체 컴퓨터 수
con: 네트워크 쌍
visited: 컴퓨터 방문 처리 배열
Map: 네트워크 쌍 저장

insert 함수

public static void insert(Map<Integer, List<Integer>> map, int s, int e){
        if(!map.containsKey(s)){
            map.put(s, new ArrayList<>());
        }
        if(!map.containsKey(e)) {
            map.put(e, new ArrayList<>());
        }
            map.get(s).add(e);
            map.get(e).add(s);
    }

매개변수 s 와 e로 들어온 컴퓨터 둘 다 key, value 값으로 하여 map에 저장한다.

virus 카운트

	...	
 	int virus = 0;
	Queue<Integer> que = new ArrayDeque<>();
    que.add(1);
    visited[1]=true;
    while(!que.isEmpty()){
    	int key = que.poll();
        if(!map.containsKey(key)){
	        continue;
        }
        for(int i: map.get(key)){
       		if(visited[i]){
            	continue;
			}
            visited[i] = true;
            que.add(i);
            virus++;
		}
	}
	System.out.println(virus);
}