[DFS/BFS] 네트워크 - JAVA

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

프로그래머스

---

요 문제도 DFS로 풀었다!

문제 처음 봤을땐 이건 BFS지~ 했는데 풀다 보니까 어쨌든 연결된 노선을 쭉~ 타고 가야하니까 깊이 우선 탐색이 맞다고 느껴졌다...^^

역시 나 아직... 감자였다구....ㅠ_ㅠ

 

아무튼 풀이과정 설명하면 다음과 같다!

 

우선 방문 표시를 해야하니까 boolean 1차원 배열을 선언해준다
그리고 노드의 개수가 n개니까 n만큼 반복문을 돌려준다
그러면서 dfs를 호출하는 데, 이 때 아직 방문하지 않은 노드만 골라서 호출해주면 된다!

그리고 dfs 함수 내에서 방문 처리를 해준 뒤, 만약 현재 노드랑 연결이 되어 있고,
방문되지 않았으면 다시 dfs를 재귀호출한다

이 때 반복문을 0부터 n까지 돌리기 떄문에 현재 노드와 탐색 중인 노드가 같지 않을 때만 호출해주는 조건을 추가해야 한다!

 

아래는 코드!

 

자바 코드)

class Solution {
    static boolean[] visited;

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

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

        return answer;
    }

    public static void dfs(int[][] computers, int x) {
        visited[x] = true;

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

    @Test
    public void test() {
        Assert.assertEquals(2, solution(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
        Assert.assertEquals(1, solution(3, new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}));
    }
}

참고한 블로그에서 테스트 코드로 테스트케이스 돌려보는게 신기해서 나도 해봤다!!

원래 main 선언해서 일일이 호출했는데 이거 좋다!!!

앞으로 알고리즘 문제 풀 때마다 테스트 코드로 해봐야지ㅎ_ㅎ