<BFS>

너비 우선 탐색 - Breadth First Search

• 시작점을 루트 노드라 생각하여, level 별로 탐색

1) 구현

✅ Queue + 인접리스트

    //인접리스트
    static Map<Integer, List<Integer>> graph = new HashMap<>();
    static Map<Integer, Boolean> visited = new HashMap<>();

    public static void bfs(int startVertex) {
        //시작점 설정
        Queue<Integer> q = new ArrayDeque<>();
        q.add(startVertex);//예약
        visited.put(startVertex, true); //방문 여부 표시 - 중복 예약 방지 (진짜 방문 후 표시X)

        while(!q.isEmpty()){ //더이상 예약이 없을 때 까지
            //방문
            int curVertex = q.remove();
            
            //다음 방문예약
            for (int nextVertex: graph.get(curVertex)) {
                if (!visited.containsKey(nextVertex)) {
                    q.add(nextVertex);
                    visited.put(nextVertex, true);
                }
            }
        }
    }

2) 문제적용

• 최단, 최소
  

---

<DFS>

깊이 우선 탐색 - Depth First Search

• 출발점에 시작, 막다른 지점에 도착할 때까지 깊게 이동

1) 구현

✅ Stack
✅ 재귀 + 인접리스트

//인접리스트
    static Map<Integer, List<Integer>> graph = new HashMap<>();
    static Map<Integer, Boolean> visited = new HashMap<>();

    public static void dfs(int curVertex) {
        //방문
        visited.put(curVertex, true);

        //현재 노드와 연결된 방문 안 한 노드 찾기
        for (int nextVertex : graph.get(curVertex)) {
            if (!visited.containsKey(nextVertex)) { //방문 안했다면
                //다음 방문 노드
                dfs(nextVertex); //재귀
            }
        }
    }

// 네트워크
	public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if(visited[i]) continue;
            dfs(n, computers, visited, i);
            count++;
        }
        return count;
    }
    
    
	void dfs (int n, int[][] computers, boolean[] visited, int cur) {
    	//방문
        visited[cur] = true;

        for (int i = 0; i < n; i++) {
            if(!visited[i] && computers[cur][i] == 1) {
                dfs(n, computers, visited, i); //재귀
            }
        }

    }