1. ๊ฐ์
์์ฃผ ๊ธฐ๋ณธ์ ์ธ BFS๋ก ํ ์ ์๋ ๊ฐ๋จํ ๋ฌธ์ ์ด๋ค. ์ด ๋ฌธ์ ๊ฐ ์ ์ ํ๋ฆฌ๋ ์ฌ๋์ BaaaaaaaaarkingDog๋์ ๊ทธ๋ํ ๊ฐ์๋ฅผ ๋ณด๊ณ ์ค๊ธธ ๋ฐ๋๋ค.
์ค๋ฒ 3๋ ์์ ๋ ํ๋ฆฌ๋ฉฐ ํ์๋ค... ์ฌํ์ด๋ ์์!
๋ด๊ฐ ํ๋ฒ ํ๋ ธ์๋๋ฐ, ์ด์ ๋ ์๋ฐฉํฅ ๊ทธ๋ํ์์ ์๊ฐํด์ฃผ์ง ์๊ณ ํ์ด์ ์ด๋ค. ์ด๋ก ์ ๋ฆฌ ๋ค์ ํด์ผ๊ฒ ๋ค.
2. ์์ค์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(br.readLine());
int E = Integer.parseInt(br.readLine());
boolean [] isVisited = new boolean[V+1];
int virusCnt = 0;
// 1) ์ธ์ ๋ฆฌ์คํธ ๋ง๋ค๊ธฐ
ArrayList<Integer> [] lists = new ArrayList[V+1];
// 2) ์ธ์ ๋ฆฌ์คํธ ์ด๊ธฐํ
for (int i = 0; i < lists.length; i++) {
lists[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
lists[from].add(to);
lists[to].add(from);
}
// 3) BFS ์์
ArrayDeque<Integer> aq1 = new ArrayDeque<>();
// 4) ๋งจ ์ฒ์ ๋ฃ๋ 1์ ๊ฒฝ์ฐ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ ํด์ฃผ๊ธฐ
aq1.add(1);
isVisited[1] = true;
while(!aq1.isEmpty()) {
int now = aq1.poll();
for (int i = 0; i < lists[now].size(); i++) {
if(!isVisited[lists[now].get(i)]){
aq1.add(lists[now].get(i));
isVisited[lists[now].get(i)] = true;
virusCnt++;
}
}
}
System.out.printf("%d", virusCnt);
}
}
0