프로그래머스 코딩테스트 연습 Level 3 - 네트워크 (JavaScript/Python)

프로그래머스 코딩테스트 연습 Level 3 - 네트워크 (JavaScript/Python)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 3 중 깊이/너비 우선 탐색(DFS/BFS) 관련 문제인,

[네트워크] 문제를 JavaScript 와 Python를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

 

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

 

작성한 답

solution.js

function solution(n, computers) {
    let answer = 0;
    const visited = Array.from({length: n}, _ => 0);
    
    const dfs = (cur) => {
        for(const i in cur) {
            if (cur[i] === 1 && visited[i] === 0) {
                visited[i] = 1;
                dfs(computers[i]);
            }
        }
    }
    
    for (const i in computers) {
        if(visited[i] === 0) {
            visited[i] = 1;
            answer++;
            dfs(computers[i]);
        }
    }
    
    return answer;
}

solution.py

def solution(n, computers):
    answer = 0
    visited = [0] * n
    
    def dfs(cur):
        for i, v in enumerate(cur):
            if v == 1 and visited[i] == 0:
                visited[i] = 1
                dfs(computers[i])
    
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
            answer += 1
            dfs(computers[i])
    
    return answer

 

설명

BFS 로 해결할 수도 있겠지만 저같은 경우 DFS를 사용하여 문제를 해결하였습니다.

DFS로 연결된 컴퓨터들을 찾아가면서 해당 컴퓨터들을 하나의 그룹으로 묶고 그렇게 형성된 그룹이 총 몇개인지를 반환한다고 생각하시면 되겠습니다.

 

현재까지 생겨난 그룹의 개수가 몇개인지를 담을 변수 answer을 0 으로 초기화 하고,

특정 컴퓨터가 이미 그룹에 속해졌는지 아닌지를 메모해둘 visited 변수를 컴퓨터의 개수만큼의 길이로 모든 값이 0 으로 초기화된 배열로 선언합니다.

이제 컴퓨터의 개수만큼 반복문을 돌기 시작하고 해당 컴퓨터가 아직 어떤 그룹에 속해져있지 않다면(해당 컴퓨터 번호의 index가 visited에서 0이다) 새로운 그룹이 생겨났다는 뜻이므로 answer을 1 증가 시키고 해당 컴퓨터는 이미 방문한 것이니 visited의 해당 index를 1로 변경합니다.

그리고 해당 컴퓨터와 연결되어있는 모든 컴퓨터를 계속해서 찾아갈 dfs 함수를 사용하여 연결된 컴퓨터를 계속해서 찾으면서 해당 컴퓨터들을 모두 이미 어떤 그룹에 속해있다는 것으로 각 컴퓨터들의 index에 대해 visited 에서 1로 만들어줍니다.

 

그렇게 모든 컴퓨터들에 대해 반복문을 돌게 되면 모든 컴퓨터는 방문이 되었을 것이고 이제 만들어진 그룹의 수에 해당하는 answer을 반환하는 것으로 문제를 해결할 수 있습니다.

 

※ 혹시 그룹을 만들고 그룹의 개수를 증가시키고 그를 반환해주는 것으로 문제를 해결한다는 것이 무슨 말인지 이해가 안되실 분들이 계실까하여 각 컴퓨터별로 몇번째 그룹에 있는지를 담아두고 그 배열을 중복 제거하는 것으로 그룹의 개수가 몇개인지를 반환하는 방법을 아래 Python 코드로 새로 작성해둡니다. 아래 코드를 보시면 위 설명이 조금 더 이해가 되실것이라 생각합니다.

그리고 아래 코드에서 group_numbering 변수를 그대로 반환하는 것으로도 문제를 해결할 수 있습니다. 보시면 아시겠지만 group_numbering 변수가 앞서 설명드린 코드에서 answer과 똑같이 사용되고 있고 visited 배열을 사용해서 해당 index의 컴퓨터가 이미 어떤 그룹에 속해있다만 판단해준 것이 아닌 group 이라는 배열에 해당 index의 컴퓨터가 몇번째 그룹에 속해있다는 것을 확인해주는 것의 차이만 있을 뿐입니다!

def solution(n, computers):
    group = [0] * n
    group_numbering = 0

    def dfs(cur):
        for i, v in enumerate(cur):
            if v == 1 and group[i] == 0:
                group[i] = group_numbering
                dfs(computers[i])

    for i in range(n):
        if group[i] == 0:
            group_numbering += 1
            group[i] = group_numbering
            dfs(computers[i])

    return len(set(group))

 

JavaScript 결과

Python 결과

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.