백준 결혼식

백준 결혼식

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의 사이즈를 받아오고 딱 레벨 단위만큼만 수행한다.

인접리스트를 활용한 dfs풀이

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]의 값으로 알 수있는 장점이 있다.

이 둘의 차이를 꼭 기억하도록 하자!

결론

레벨단위의 탐색 수행

재귀를 활용한 depth를 줘서 탐색해보자

BFS를 활용해서 탐색해보자

인접행렬은 탐색의 범위가 넓어지기 때문에 재귀로 풀게되면 틀릴 가능성이 있다. vis를 잘 활용해도 재탐색하는 경우가 발생하기 때문이다.

재귀 + 인접리스트

인접리스트 / 인접행렬 + BFS

위의 방법으로 문제를 앞으로 풀어나가도록 하자!

참고

인접 행렬과 인접 리스트