import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.SQLOutput;
import java.util.*;
class Main {
static int [] vis;
static ArrayList<Integer> store;
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int V = Integer.parseInt(br.readLine());
vis = new int[N+1];
store = new ArrayList<>();
int [][] arr = new int[N+1][N+1];
for(int i=0; i<V;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] =1;
arr[y][x]=1;
}
count=0;
find(1,arr);
// for(int x : vis){
// System.out.print(x + " ");
// }
System.out.println(--count<0? 0 : count );
}
private static void find(int start,int [][] arr){
Queue<Integer> q = new LinkedList<>();
q.add(start);
int depth=0;
while(!q.isEmpty() && depth<2){
int size = q.size();
depth++;
for(int i=0;i <size ;i++){
int cur = q.poll();
for(int k=1; k<arr.length; k++){
if(arr[cur][k] ==1 && vis[k]==0){
vis[k]=1;
q.add(k);
count++;
}
}
}
}
}
}
친구의 친구 즉 2단계 까지만 탐색하면 된다.
그래서 레벨단위로 탐색하기 좋은 BFS를 사용했다.
while(!q.isEmpty() && depth<2){
int size = q.size();
depth++;
for(int i=0;i <size ;i++){
int cur = q.poll();
for(int k=1; k<arr.length; k++){
if(arr[cur][k] ==1 && vis[k]==0){
vis[k]=1;
q.add(k);
count++;
}
}
}
}
기존에는 while문으로 Q가 빌때까지 계속 수행했었따면 지금은 size변수로 Q의 사이즈를 받아오고 딱 레벨 단위만큼만 수행한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.SQLOutput;
import java.util.*;
class Main {
static int [] vis;
static ArrayList<Integer> store;
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int V = Integer.parseInt(br.readLine());
vis = new int[N+1];
store = new ArrayList<>();
int [][] arr = new int[N+1][N+1];
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0; i<=N; i++){
ArrayList<Integer> ar = new ArrayList<>();
list.add(ar);
}
for(int i=0; i<V;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
//arr[x][y] =1;
//arr[y][x]=1;
list.get(x).add(y);
list.get(y).add(x);
}
count=0;
dfs(1,list,0);
for(int i=2; i<vis.length; i++){
if(vis[i] ==1)count++;
}
System.out.print(count);
}
private static void dfs(int start, ArrayList<ArrayList<Integer>> list, int depth){
if(depth ==2)return;
for(int x : list.get(start)){
vis[x]=1;
dfs(x, list,depth+1);
}
}
}
}
이때 인접 행렬로 풀면 문제를 틀리게된다!
그 이유는 인접 행렬은 vis배열을 잘 사용해도 탐색 범위가 넓어 방문한 노드를 다시 탐색할 가능성이 높아질 수 있기 때문이다.
탐색 범위가 넓은 이유는 N*N
의 형태로 이루어져 있기 때문이다. 즉 내가 찾는 노드가 어떤 노드와 연결되어 있는지 직관적으로 알기위해서는 인접리스트를 사용하는 것이 좋다.
다시 말하지만 인접리스트와 인접 행렬의 차이점은
인접 리스트일때는 각 노드가 어떤 노드와 연결되어 있는지 알 수 있다. 대신에 임의의 노드 N과 K가 연결되어 있는지 확인하려면 노드가 연결되어 있는지 직접 탐색으로 알아야한다.
인접행렬은 N*N
으로 불필요한 탐색의 범위가 생길 수도 있다. 하지만 임의의 노드 N과 K가 연결되어있는지 node[N][K]
의 값으로 알 수있는 장점이 있다.
이 둘의 차이를 꼭 기억하도록 하자!
위의 방법으로 문제를 앞으로 풀어나가도록 하자!