[알고리즘_프로그래머스] DFS/BFS - 네트워크

코딩부트캠프는 단기간에 준비하느라 파이썬으로 통과를 했지만, 나는 백엔드 쪽을 희망하기에 앞으로, JAVA로 차근차근 코테 문제를 풀어보려고 한다. 요즘 캡스톤 프로젝트를 하느라 몸도 마음도 바빠지기 시작했지만 그래도 스터디 덕에 시간을 내서 문제를 풀 것이다. 오늘 풀 문제는 프로그래머스의 네트워크 문제인데 DFS/BFS 개념을 이용하는 문제다.

 

 

문제 설명

 

컴통(컴퓨터통신)의 스위칭 그림도 생각난다ㅏ

 

 

[최종 코드]

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n]; // 방문 여부를 저장할 배열
        int networkCount = 0; // 네트워크 개수를 저장할 변수
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 아직 방문하지 않은 컴퓨터라면
                dfs(i, computers, visited); // DFS를 통해 연결된 컴퓨터들을 모두 방문 처리
                networkCount++; // 새로운 네트워크 발견했으므로 증가
            }
        }
        
        return networkCount;
    }
    
    // DFS 탐색 함수
    void dfs(int current, int[][] computers, boolean[] visited) {
        visited[current] = true; // 현재 컴퓨터 방문 처리
        
        for (int i = 0; i < computers.length; i++) {
            // 현재 컴퓨터와 연결된 다른 컴퓨터 중 방문하지 않은 컴퓨터가 있으면 DFS 재귀 호출
            if (computers[current][i] == 1 && !visited[i]) {
                dfs(i, computers, visited);
            }
        }
    }
}

 

 

[설명]

 

• 각 컴퓨터를 순회하면서, 방문하지 않은 컴퓨터는 새로운 네트워크의 시작점으로 간주하고 dfs 함수로 탐색 시작.
• dfs는 현재 컴퓨터에서 연결된 모든 컴퓨터를 방문하며, 같은 네트워크로 묶는다.
• 중복 탐색을 피하기 위해 방문 여부를 체크하는 visited 배열을 사용

 

 

보통 BFS(너비 우선 탐색)는 큐로, DFS(깊이 우선 탐색)은 스택이나 재귀함수를 이용해 푼다. 앞으로 다양한 문제들을 접하면서 배운 자료구조를 알고리즘을 푸는데 더 잘 사용할 수 있도록 하고싶다!