[알고리즘 문제 풀이] 프로그래머스 - 네트워크

원문 링크: programmers.co.kr/learn/courses/30/lessons/43162

카테고리: DFS/BFS

 

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미한다. 예를 들어, 컴퓨터 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로 표현한다.
• compter[i][i]는 항상 1이다.

입출력 예

int n = 3; int[][] computers = {{1,1,0}, {1,1,0}, {0,0,1}}; // return = 2
int n = 3; int[][] computers = {{1,1,0}, {1,1,1}, {0,1,1}}; // return = 1

 

입출력 예 설명

예제 #1

예제 #2

 

풀이 과정

처음에 너무 삽질을 했다. DFS나 BFS를 이용하지 않고 HashMap을 이용해서 풀 수 있을 것 같았다. 희안하게도 13개의 테스트 케이스 중에 11개가 통과하는 바람에 코드를 더 개선해보려고 애를 쓰느라 시간을 많이 보냈다. 테스트케이스에서는 많이 맞췄지만 결과적으로 내 코드를 살펴보니 특정 케이스에서는 풀 수 없다고 판단되었다. 그러고 나서야 결국 DFS를 이용하기로 했다.  

 

재귀호출 방식이 익숙하지 않아서 stack을 사용해서 풀어보기로 했다. 종이에 그림을 그려가며 풀이 방법을 생각하다보니 어느정도 감이 잡혔다. stack에 검사할 컴퓨터의 위치를 넣고 빼가면서 탐색을 하고 탐색을 마치면 answer의 숫자를 늘려가면 되겠다고 생각했다. 그런데 어느 시점에 stack.pop()을 해야할지가 조금 아리송했다. 그래서 코드 구현이 바로 되질 않았다. 항상 느끼는 거지만 풀이 방법을 정확하게 설명할 수 없다면 코드로도 구현할 수 없다. 당연한 일이다. 그래서 다시 종이에 로직을 정리했다.  

 

대략적인 로직은 아래와 같다.

• 네트워크의 개수 answer는 0부터 시작한다.
• 각 컴퓨터의 검사여부 확인을 위해 boolean[] check을 n의 크기를 가지도록 생성한다.
• 검사 기준이 될 컴퓨터를 0 부터 차례대로 stack에 넣는다(push).
• while문을 stack에 데이터가 있는 동안 반복한다.
• while문이 시작함과 동시에 stack에서 데이터를 꺼내고(pop), 비교 대상이되는 컴퓨터를 다시 0부터 차례대로 검사한다.
• 비교 대상 컴퓨터와 검사 기준 컴퓨터가 연결되어있다면 그 컴퓨터도 검사를 해야되기 때문에 stack에 넣는다.
• stack에 있는 모든 컴퓨터를 검사했다면 하나의 네트워크에 속한 컴퓨터를 모두 확인한 것이기 떄문에 answer에 1을 더한다. 

위와 같은 방법을 사용하면 앞에서 이미 검사한 컴퓨터는 뒤에서 다시 검사하지 않기 때문에, 하나의 네트워크에 속한 컴퓨터를 모두 찾아내서 개수를 셀 수 있고, 그 뒤에는 다른 네트워크에 속한 컴퓨터만 검사 대상에 포함되게 된다.

 

자바 코드

public int solution(int n, int[][] computers) {
    int answer = 0;
    boolean[] check = new boolean[n]; // 검사 여부를 확인할 목적으로 사용
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < n; i++) {
        if (!check[i]) { // 검사 안한 항목만 진행
            check[i] = true;
            stack.push(i);

            while (!stack.isEmpty()) {
                int target = stack.pop();
                for (int j = 0; j < n; j++) {
                    if (i != j && computers[target][j] == 1 && !check[j] ) {
                        stack.push(j);
                        check[j] = true;
                    }
                }
            }

            answer++; // 끝까지 탐색했으면 네트워크 개수 추가
        }
    }

    return answer;
}

 

채점 결과

 

참고

- 깃허브 소스 코드: 링크