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--;
}
...
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);
}
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);
}
문제에서 1번 컴퓨터가 숙주 컴퓨터라고 했으니, que에 1을 넣고 방문처리를 해주면서 시작한다.
map에 현재 1번에 들어있는 list를 순회한다.
해당 컴퓨터를 이미 방문한 경우는 건너뛰고, 그렇지 않은 경우 que에 삽입 & 방문처리 한다.
virus
변수를 1씩 증가한다.
que에 남아 있는 원소가 없을 때까지 반복하고, virus를 반환하며 종료한다.
양방향인 걸 알았는데 양방향으로 구현을 안 해서 오래 걸렸다.
그냥 쉽게 갈걸... ..
그래도 풀어서 기분 조타