[Network]

 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

풀이 과정

우선 문제 자체를 잘 이해해보자. 나는 개인적으로 프로그래머스에서 예시로 나와있는 그림을 보니까 더 헷갈렸는데, 배열로만 보았을 때는 더 이해하기 쉬웠다!

그러니까 문제를 풀기 위해서는,

(1) 우선 다 false인 boolean 배열을 만들어서(체크되었는지 확인을 위해),
(2) for문으로 컴퓨터 한개씩 반복문을 돌면서,
(3) 내가 아니고(제한 사항 참고) && 컴터 배열값이 1이면(연결되었다는 의미) 재귀호출(완전탐색)을 진행한다.
(4) 그렇게 새로운 네트워크가 발견될 때마다 answer가 증가하고 그 값을 반환하면 된다. 

나는 지난번에 풀었던 dfs 기본 공식을 바탕으로 문제를 해결하려고 노력했다. 

맨처음에는 dfs 쌩 틀에다가 visited를 체크할 배열을 추가하고, dfs 메서드 안에서 언제 재귀함수를 호출하는지 조건을 생각한다. 나는 네트워크 즉 answer를 언제 늘려야하는지를 잘못 판단해서 처음에 에러가 나오기도 했었다.  

해당 내용을 코드로 적기

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

        for (int i = 0; i < n; i++) { // n개 컴퓨터 - n번 돌면서 탐색하기
            if (!visited[i]) { // 안가본곳 가야지~
                dfs(computers, i, visited);
                answer++;
            }
        }
        return answer;
    }

    void dfs(int[][] computers, int i, boolean[] visited) {
        visited[i] = true; // 방문했슴다~

        for (int j = 0; j < computers.length; j++) { // 컴퓨터길이만큼 돌면서 탐색
            if (i != j && computers[i][j] == 1 && !visited[j]) { // !자기자신 && 컴터 배열값=1 && visited false면 재귀호출
                dfs(computers, j, visited);
            }
        }
    }
}

 

3단계는 처음인데 처음 겁먹은거치곤 코드도 생각보다 짧게 나왔고, 지난번 책임님께 배워둔 dfs 공식대로 하니까 풀만 했던 것 같다! 특히, 어렵게 생각하지 말고 조건문과 반복문의 포인트만 잡아내면 익숙해질 수도 있을 것 같다..!

3단계 중 가장 쉬운 문제였지만 점점 더 열심히 풀어서 어려운 문제들도 뚝딱뚝딱 풀고싶다 :)