그래프 문제일때 생각해볼 것

그래프와 탐색 그래프 = 정점 + 간선
디그리의 합 = 모든 간선 갯수의 2배, 이걸로 시간복잡도를 계산

그래프 저장 - 인접 행렬, 인접 리스트 2가지가 가능하다
인접 행렬은 2차원 배열, 인접 리스트는 큐 형태

인접행렬 - 공간복잡도 정점 갯수의 제곱, arr[1,3] <- 1번 정점에서 3번으로 갈 수 있다
인접 리스트 - 리스트 형태로 이어진 정점을 저장, 인접리스트는 2차원 ArrayList
ArrayList<ArrayList<Integer>> list 형태로 저장, 필요한 공간은 차수의 합 = 간선 2배만큼 필요

간선 존재 여부를 확인해야되면 인접 행렬이 좋고 모든 정점을 확인해야하면 인접 리스트를 쓰는게 좋지만 
인접행렬은 공간복잡도가 정점 갯수의 제곱이고 인접리스트는 간선 갯수의 2배라 공간복잡도를 잘 생각해야한다

그래프라고 대놓고 말  안하고 마을과 도로 등으로 정점과 간선이 들어오니잘 파악해야한다
그래프를 저장하는 방식도 인접 행렬과가 인접 리스트 중 뭘 쓸지를 잘 생각해야한다

그래프 탐색 - 시작 정점에서 간선을 타고 갈 수 있는 정점이 무엇인지 탐색

dfs의 경우에는 인접 리스트로 가는게 시간복잡도 측면에서 훨씬 좋다

• dfs 뼈대 코드, 2차원 Arraylist를 사용한다

    static boolean[] visited = new boolean[100];
    static int[] arr = new int[100];

    static void dfs(int x){
        // visited = true 로 해주는 연산은 한번씩만 체크된다
        visited[x] = true;

        for (int y: arr){
            // 이미 방문한 정점은 지나가고
            if (visited[y]) continue;
            dfs(y);
        }
    }

 

• bfs 뼈대 코드, 큐를 사용한다

! 큐에 넣을때 방문한걸 체크 - visited를 true로 바꾼다

 static boolean[] visited = new boolean[100];
    static int[] arr = new int[100];

    static void bfs(int start){
        Queue<Integer> queue = new LinkedList<>();

        //처음에 방문하는 start를 큐에 넣고 시작한다
        queue.add(start);
        visited[start] = true; // 큐에 넣은건 방문한 배열이다
        
        //더 방문할 정점이 없을 때 까지
        while (!queue.isEmpty()){
            int x = queue.poll();

            for (int y : x에서 갈 수 잇는 정점){

                //이미 방문한 정점이면 지나가고
                if (visited[y]) continue;

                //갈수 있으면 큐에 집어넣고 방문 처리하기
                queue.add(y);
                visited[y] = true
            }
        }
    }