[알고리즘] 프로그래머스 네트워크 -dfs, bfs-

 

 

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20-bfs%2Cdfs-

https://programmers.co.kr/learn/courses/30/lessons/43162?language=kotlin

코딩테스트 연습 - 네트워크

 

 

 

BFS 를 사용하여 처음 연결된 곳이 생길 경우 총 네트워크 개수의 -1 을 해주어 해결했습니다. ㅎㅎ

 

풀이방법은 다음과 같습니다. 

 

[Java]

class Solution {
    private static int[][] map;
    private static boolean[] isVisited;
    private static int n;
    private static int answer = 0;

    private static void dfs(int start) {
        if (isVisited[start]) {
            return;
        }
        isVisited[start] = true;
        for (int j = 0; j < n; j++) {
            if (map[start][j] == 1 && isVisited[j] == false) {
                dfs(j);
                answer--; // 붙어 있는거면 전체 네트워크 개수 - 1
            }
        }
    }

    public int solution(int n, int[][] computers) {
        Solution.n = n;
        map = new int[n][n];
        isVisited = new boolean[n];
        answer = n;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = computers[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            dfs(i);
        }
        System.out.println(answer);
        return answer;
    }
}

 

 

[Kotlin]

internal class Solution {

    fun solution(n: Int, computers: Array<IntArray>): Int {
        Solution.n = n
        map = Array(n) { IntArray(n) }
        isVisited = BooleanArray(n)
        answer = n

        for (i in 0 until n) {
            for (j in 0 until n) {
                map[i][j] = computers[i][j]
            }
        }
        for (i in 0 until n) {
            dfs(i)
        }
        return answer
    }

    companion object {
        private lateinit var map: Array<IntArray>
        private lateinit var isVisited: BooleanArray
        private var n: Int = 0
        private var answer = 0

        private fun dfs(start: Int) {
            if (isVisited[start]) {
                return
            }
            isVisited[start] = true
            for (j in 0 until n) {
                if (map[start][j] == 1 && isVisited[j] == false) {
                    dfs(j)
                    answer-- // 붙어 있는거면 전체 네트워크 개수 - 1
                }
            }
        }
    }
}

 

 

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20-bfs%2Cdfs-

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!!