https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
dfs랑 bfs 둘 다 풀어봤다.
시간을 줄이기 위해서 BufferedReader쓰고 StringTokenizer로 받아줬고,
방문체크 잘 해주고 답 출력할 때 자기 컴퓨터는 빼고 계산해야하니까 1 빼주면 된다!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N,M;
static ArrayList<Integer>[] arr;
static Queue<Integer> q;
static boolean[] visit;
static int result=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new ArrayList[N+1];
visit = new boolean[N+1];
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for(int i=1;i<=N;i++){
arr[i]=new ArrayList<>();
}
for(int i=0;i<M;i++){
st=new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
arr[u].add(v);
arr[v].add(u);
}
//dfs(1);
bfs();
System.out.println(result-1);
}
public static void dfs(int v){
visit[v]=true;
++result;
for(int i=0;i<arr[v].size();i++){
int nxt = arr[v].get(i);
if(!visit[nxt]){
visit[nxt]=true;
dfs(nxt);
}
}
}
//bfs로 풀기
public static void bfs(){
q = new LinkedList<Integer>();
q.add(1);
while(!q.isEmpty()){
int cur = q.poll();
visit[cur]=true;
result++;
for(int i=0;i<arr[cur].size();i++){
int nxt = arr[cur].get(i);
if(!visit[nxt]){
visit[nxt]=true;
q.add(nxt);
}
}
}
}
}
|
cs |