7. 프로그래머스 - 네트워크

문제 설명  네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.  예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.  따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[ i ][ j ]를 1로 표현합니다. 1 : [1, 1, 0] 2 : [1, 1, 0] 3:  [0, 0, 1]

문제 해결 1. 모든 컴퓨터를 순차적으로 검색 시작 2. 네트워크의 수를 1 증가 시킨 뒤 대상과 연결된 모든 컴퓨터를 DFS를 이용해서 검색 3. 대상과 직 간접적으로 연결된 모든 컴퓨터는 검색체크함 4. 해당 네트워크의 검색이 종료된 후 다른 컴퓨터를 검색 시작 5. 이미 검색된 컴퓨터를 제외하고 아직 검색되지 않은 컴퓨터를 검색 후 2번부터 반복

    bool[] ischeck = new bool[200];

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

        //검사
        for (int i = 0; i < n; ++i)
        {
            //아직 검사를 하지 않았다면
            if (!ischeck[i])
            {
                //검사체크, 네트워크 +1, 세부 검사
                ischeck[i] = true;
                ++answer;
                DFS(i, n, ref computers); ;
            }
        }

        return answer;
    }

    public void DFS(int num,int n, ref int[,] computers)
    {
        //하위(현재)요소 검색
        for(int i = 0; i < n; ++i)
        {
            //아직 검사하지 않았고, 상위요소와 연결되어 있다면
            if (!ischeck[i] &&
                computers[num,i] == 1)
            {
                ischeck[i] = true;
                DFS(i, n, ref computers);
            }
        }
    }

 

 

평소엔 잘 사용하지 않는 재귀를 이용한 DFS를 사용해봤다. 계속 안쓸 수는 없으니 이참에 한번 해봐야지 하고 했는데 안쓰던걸 써서 그런가 갑자기 생각이 꼬여서 쓸데없이 시간이 오래 걸렸다.

그리고 3레벨 부터는 역시 난이도가 있다는 느낌이 드는데 막상 풀고보면 왜 이런거에 이렇게 낑낑댔지 싶은 생각이 들어서 자괴감이 든다.