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

---

📄 문제

네트워크

 

💡 풀이

DFS(깊이 우선 탐색) 알고리즘을 사용하여 네트워크를 탐색하고, 연결된 그룹을 찾아 answer 변수에 저장한 후 반환합니다.

 

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); // DFS로 연결된 모든 컴퓨터를 방문
                answer++; // 네트워크 개수 증가
            }
        }

        return answer;
    }

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

        for (int i = 0; i < computers.length; i++) {
            if (computers[node][i] == 1 && !visited[i]) {
                dfs(i, computers, visited); // 연결된 컴퓨터를 재귀적으로 방문
            }
        }
    }
}

 

◾ 코드 설명

 

[예시]

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2

1. 배열 초기화: `visited = [false, false, false]`
2. `solution` - `for` 루프 (i=0):

• `if visited[0] == false` 이므로 조건 만족
• `dfs` 함수 호출: `dfs(0, computers, visited)`
  • `visited[0]`을 `true`로 변경하여 방문 처리
  • `for` 루프 (i=0):
    • `if visited[0] == true` 이므로 조건 불만족
  • `for` 루프 (i=1):
    • `if computers[0][1] == 1 && visited[1] == false` 이므로 조건 만족
    • `dfs` 함수 호출: `dfs(1, computers, visited)`
      • `visited[1]`을 `true`로 변경하여 방문 처리

---

• answer 값 증가: answer = 1

3. `solution` - `for` 루프 (i=1):

• `if visited[1] == true` 이므로 조건 불만족

4. `solution` - `for` 루프 (i=2):

• `if visited[2] == false` 이므로 조건 만족

---

• answer 값 증가: answer = 2