[Programmers: JAVA] 네트워크

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

위 문제와 유사하다는 생각이 들었다

위 문제는 플로이드-워샬 알고리즘으로 풀었는데 이번에는 DFS/BFS 연습을 위해 다르게 풀어보도록 하겠다

---

DFS

- 추후 개선해야 할 코드이긴 하나 일단 올림

 

이런 방향으로 짜봄

 

public class Solution {
    static int answer;
    static boolean visited[];

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

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

        return answer;
    }

    public static void DFS(int a, int[][] computers, int n){
        if(a == n) return;
        for (int i = 0; i < n; i++) {
            if(a != i && computers[a][i] == 1 && !visited[i]){
                visited[i] = true;
                DFS(i, computers, n);
            }
        }
}

 

 

동일한 코드를 중복해서 쓴 부분을 고칠 수 있을 것 같은데... 지금은 머리가 안 돌아감