[Lv.3] 네트워크 : Java

프로그래머스

 

 

 

이해하기

Lv.3...? 내가 이걸 풀 수 있을까? 라는 생각부터 들었다.

물론 못 풀었다ㅋㅋ (그래도 쫄지 말 것!)

 

[프로그래머스] 네트워크 문제풀이 (Java)

정리를 너무 잘해주신 글이 있어서 참고해서 풀이하였다!

알고리즘 풀이 순서만 읽어도 어떻게 구현해야 할지가 한 눈에 파악되도록 정리해주셨다❤️

어떻게 해야 이렇게 풀이 방법을 떠올리고, 정리하고, 구현할 수 있을까...

 

1. n 개수만큼 방문을 체크할 boolean 배열을 만들고 모든 요소를 false로 초기화한다.
2. n만큼 for문을 돌다가 visited[i]값이 false인게 있으면 깊이 dfs 호출 & answer++
   • dfs 파라미터 : computer[][], i, visited[]
3. 전달받은 visited[i]를 true로 바꿔준다.
4. computer의 길이만큼 반복문을 돈다.
5. 아래 조건을 모두 만족하면 재귀 호출!
   • 자기 자신이 아님
   • visited 값이 false (아직 방문X)
   • computer 배열의 값이 1 (연결되어 있을 것)

 

문제풀이

class Solution {
    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]) {
                dfs(computers, i, visited);
                answer++;
            }
        }

        return answer;
    }

    boolean[] dfs(int[][] computers, int i, boolean[] visited) {
        visited[i] = true;

        for (int j = 0; j < computers.length; j++) {
            if (i != j && computers[i][j] == 1 && !visited[j]) {
                visited = dfs(computers, j, visited);
            }
        }
        return visited;
    }
}

 

        int answer = 0;
        boolean[] visited = new boolean[n];

 

answer와 visited 배열 선언!

 

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

 

for문을 돌며 아직 방문하지 않은 곳이면 dfs 함수를 호출하고 answer++ 해준다.

 

    boolean[] dfs(int[][] computers, int i, boolean[] visited) {
        visited[i] = true;

 

해당 위치를 방문 처리 해주고,

 

        for (int j = 0; j < computers.length; j++) {
            if (i != j && computers[i][j] == 1 && !visited[j]) {
                visited = dfs(computers, j, visited);
            }
        }

 

1. 자기 자신이 아니고
2. 서로 연결되어 있으며
3. 아직 방문하지 않은

노드라면 dfs를 재귀호출해준다. (이 때, 인덱스를 j로 바꿔줄 것)

 

 

 

위에서 정리해주신 순서대로 풀이하면 쉽게 느껴진다.

나도 저렇게 풀이하고 싶다...!!