[프로그래머스: DFS/BFS] 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

# DFS 코드

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n]; // 각 컴퓨터의 방문 여부 체크 배열
        int answer = 0;

        for (int i = 0; i < n; i++) {
            // 아직 방문하지 않은 컴퓨터라면
            if (!visited[i]) {
                dfs(i, computers, visited); // 해당 컴퓨터 i를 시작점으로 연결된 모든 컴퓨터를 탐색함
                answer++; // 네트워크 개수 ++
            }
        }

        return answer;
    }

    // DFS로 연결된 모든 컴퓨터 방문 처리
    public void dfs(int curr, int[][] computers, boolean[] visited) {
        visited[curr] = true; // 현재 컴퓨터 방문 처리

        // 전체 컴퓨터를 돌며 연결된 컴퓨터 탐색
        for (int j = 0; j < computers.length; j++) {
            // 현재 컴퓨터와 연결되어 있고, 아직 방문하지 않은 컴퓨터라면
            if (computers[curr][j] == 1 && !visited[j]) {
                dfs(j, computers, visited); // 연결된 컴퓨터 j를 기준으로 DFS
            }
        }
    }
}

• DFS/BFS 모두 방문 여부를 체크하는 visited 배열이 2차원이 아니라 1차원인 이유 : 방문 여부를 각 컴퓨터별로 한 번만 체크하면 되기 때문이다. 연결된 컴퓨터끼리는 1개의 네트워크로 묶이기만 하면 끝이고, 이미 방문한 컴퓨터는 다시 탐색할 필요가 없다 !
• 방문할 대상이 '노드 단위'이기 때문에 visited 배열도 1차원으로 충분한 것이다.
• 반면, 미로 문제처럼 '경로'를 기준으로 움직이는 경우에는 2차원 visited 가 필요하다.

 

 

 

# BFS 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n]; // 각 컴퓨터의 방문 체크 여부
        int answer = 0;
        
        for (int i = 0; i < n; i++) {
            // 아직 방문하지 않은 컴퓨터라면
            if (!visited[i]) {
                bfs(i, computers, visited); // 해당 컴퓨터 i를 시작점으로 연결된 모든 컴퓨터를 탐색함
                answer++; // 네트워크 개수 ++
            }
        }

        return answer;
    }

    // BFS로 연결된 컴퓨터들을 방문 처리
    public void bfs(int start, int[][] computers, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>(); // 탐색을 위한 큐 생성
        q.offer(start); // 시작점 큐에 추가
        visited[start] = true; // 시작점 방문 처리

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            int curr = q.poll(); // 현재 컴퓨터 꺼내기

            // 전체 컴퓨터를 돌며 연결된 컴퓨터 탐색
            for (int j = 0; j < computers.length; j++) {
                // 연결되어 있고 아직 방문하지 않았다면
                if (computers[curr][j] == 1 && !visited[j]) {
                    q.offer(j); // 큐에 추가
                    visited[j] = true; // 방문 처리
                }
            }
        }
    }
}