[코딩테스트] 네트워크

문제

---

네트워크 문제 바로가기

제출 코드(JAVA)

---

코드 제출

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] check = new boolean[computers.length];

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

    private void dfs(int[][] computers, boolean[] check, int i) {
        check[i] = true;

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

1) 방문한 노드인지 탐색하는 check배열 생성
2) 노드만큼 반복문 진행
3) 방문한 노드는 true 변경 후, 각 조건에 맞으면 재귀 실행

• 자신을 바라보는 간선이 아니고 ( i != j )
• 연결되어 있는 간선인가 (computers[i][j] == 1)
• 탐색한적 없는 간선인가 (check[j] == false)

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.04ms, 52.7MB)
테스트 2 〉	통과 (0.04ms, 51.9MB)
테스트 3 〉	통과 (0.04ms, 53MB)
테스트 4 〉	통과 (0.04ms, 52.9MB)
테스트 5 〉	통과 (0.02ms, 52.7MB)
테스트 6 〉	통과 (0.13ms, 52.2MB)
테스트 7 〉	통과 (0.03ms, 52.1MB)
테스트 8 〉	통과 (0.08ms, 53.2MB)
테스트 9 〉	통과 (0.10ms, 52.5MB)
테스트 10 〉	통과 (0.06ms, 54.2MB)
테스트 11 〉	통과 (0.34ms, 54.1MB)
테스트 12 〉	통과 (0.27ms, 54.3MB)
테스트 13 〉	통과 (0.14ms, 54.4MB)

그래프부터는 생소해서 다른 답안을 참조하며 공부와 함께 진행하는 중...

제출 코드(Python)

---

코드 제출

from collections import defaultdict

def dfs(computers, check, i):
    check[i] = True

    for j in range(len(computers)):
        if i != j and computers[i][j] == 1 and check[j] == False:
            dfs(computers, check, j)


def solution(n, computers):
    result = 0
    check = defaultdict(lambda: False)

    for i in range(n):
        if not check[i]:
            dfs(computers, check, i)
            result += 1

    return result

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.07ms, 10.2MB)
테스트 4 〉	통과 (0.07ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.31ms, 9.93MB)
테스트 7 〉	통과 (0.03ms, 10.2MB)
테스트 8 〉	통과 (0.22ms, 10.2MB)
테스트 9 〉	통과 (0.14ms, 10.2MB)
테스트 10 〉	통과 (1.77ms, 10.1MB)
테스트 11 〉	통과 (0.97ms, 10.1MB)
테스트 12 〉	통과 (0.86ms, 10.3MB)
테스트 13 〉	통과 (0.44ms, 10.2MB)