[프로그래머스/JAVA] 네트워크

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

프로그래머스

---

- 문제 풀이

1. 모든 컴퓨터를 한 번씩 방문합니다.
2. 방문한 컴퓨터와 연결된 컴퓨터들을 탐색해 같은 네트워크로 묶습니다.
3. 방문하지 않은 컴퓨터를 만나면 새로운 네트워크로 간주합니다.
4. DFS(깊이 우선 탐색)를 사용해 각 네트워크를 탐색합니다.

 

+ DFS가 필요한 이유?

DFS를 사용하면 한 컴퓨터에서 시작해 연결된 모든 컴퓨터를 방문할 수 있습니다. 이때 방문한 컴퓨터는 다시 방문하지 않도록 체크합니다.

 

---

 

 

 

1. 한 네트워크 탐색

public void dfs(int node, boolean[] visited, int[][] computers) {
    visited[node] = true;  // 현재 컴퓨터 방문 처리

    for (int i = 0; i < computers.length; i++) {
        // 아직 방문하지 않았고 연결된 컴퓨터이면 재귀 호출
        if (!visited[i] && computers[node][i] == 1) {
            dfs(i, visited, computers);
        }
    }
}

• 한 컴퓨터에서 시작해 연결된 모든 컴퓨터를 방문합니다.
• 방문한 컴퓨터는 visited 배열에 표시합니다.
• 연결된 컴퓨터가 있으면 재귀 호출로 탐색을 이어갑니다.

 

 

 

 

ex) 입력 예시

int[][] computers = {
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 1}
};

 

탐색 과정

1. 0번 컴퓨터에서 시작 (visited = [false, false, false]):
   • 0번 컴퓨터를 방문 (visited[0] = true)
   • 1번 컴퓨터와 연결되어 있으므로 1번도 방문 (visited[1] = true)
2. 1번 컴퓨터에서 탐색 종료:
   • 1번 컴퓨터에서 연결된 컴퓨터는 이미 모두 방문했으므로 종료.
3. 2번 컴퓨터 탐색:
   • 아직 방문하지 않았으므로 새로운 네트워크로 간주 (answer++)
   • 2번 컴퓨터는 혼자이므로 탐색 종료.

 

최종 네트워크 개수

• 첫 번째 네트워크: 0번 ↔ 1번
• 두 번째 네트워크: 2번

정답: 2

 

 

 

 

2. 전체 네트워크 탐색

public int solution(int n, int[][] computers) {
    int answer = 0;  // 네트워크 개수를 저장할 변수
    boolean[] visited = new boolean[n];  // 방문 여부를 기록하는 배열

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {  // 방문하지 않은 컴퓨터가 있다면
            answer++;  // 새로운 네트워크 발견
            dfs(i, visited, computers);  // 해당 컴퓨터에서 DFS 탐색 시작
        }
    }
    return answer;  // 최종 네트워크 개수 반환
}

• 모든 컴퓨터를 순회하면서 방문하지 않은 컴퓨터가 있다면 새로운 네트워크로 간주합니다.
• DFS로 해당 컴퓨터와 연결된 컴퓨터들을 모두 방문합니다.
• 방문할 때마다 네트워크 개수를 하나씩 증가시킵니다.

 

 

---

 

 

- 정답 코드

class Solution {
    // 한 컴퓨터에서 DFS 탐색을 시작하면, 그 컴퓨터와 연결된 모든 컴퓨터를 방문
    public void dfs(int node, boolean[] visited, int[][] computers) {
        // node = 0, 즉 컴퓨터 0을 방문
        visited[node] = true; // visited = [true, false, false]

        for (int i = 0; i < computers.length; i++) {
// i번째 컴퓨터가 아직 방문되지 않았고, 현재 컴퓨터와 연결되어 있으면 DFS 재귀 호출
            if (!visited[i] && computers[node][i] == 1) {
                dfs(i, visited, computers);
            }

            // computers[0][0] == 1은 이미 방문 상태이므로 재귀 호출x
            // computers[0][1] == 1)은 방문되지 않았고,
            //                       컴퓨터 0과 연결되어 있으므로 재귀 호출
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;

        // 탐색할 때 사용한 컴퓨터는 다시 방문하지 않도록 체크하기 위해
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if(!visited[i]) {
                answer++;
                dfs(i, visited, computers);
            }
        }
        return answer;
    }
}