프로그래머스 : 네트워크

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

 

유니온 파인드로도, dfs로도 풀 수 있는 문제다.

필자는 유니온 파인드를 시도했다가 못풀고 dfs로 풀었다.

 

dfs를 하기 위한 방법 중 하나는 재귀함수를 쓰는 것이다.

이번엔 재귀에 대해서 좀 더 생각해보자.

 

재귀는 참 공부를 해도 헷갈리는 녀석이다.

그래서 이참에 마무리를 지어버리려고 한다.

 

내가 생각한 재귀는 '분신을 만들고 일을 시키는 것' 이다.

A라는 함수는 실행도중 자신의 분신을 만들고, 자신과 똑같은 일을 시킨다. 그러면 그 분신도 또 자신의 분신을 만들고 그에게 일을 똑같은 일을 시킨다. 만약 조건이 없다면 이는 무한반복 될 것이다.

때문에 재귀에는 어떤 조건에 도달하면 리턴하는 로직이나 함수를 끝내는 로직이 반드시 필요하다.

 

그렇게 함수가 끝나면 자신에게 일을 시켰던 상위 분신에게 자기가 일을 끝냈다고 말한다. 만약 리턴값이 있는 함수면 일한 결과를 return으로 던져준다. 상사에게 일을 보고하는 이미지를 생각하면 이해가 쉬울 것이다.

상위 분신, 즉  상사는 놀랍게도 나에게 일을 시킨뒤에 아무것도 하지 않고 그대로 멈춰있었고, 내가 업무보고를 하고나서야 그 결과를 토대로 남은 일을 시작한다. 그 일이 끝나면 상사 또한 그 상사에게 업무결과를 리턴한다. 그러면 그 상사는 또 상사에게.. 하는 것이 반복되다가 마침내 최초 오리지널에게 최종결과가 보고되고, 재귀함수가 끝이난다.

 

 

그림자 분신술!

 

자 이런 점을 염두에 두고 문제를 보자.

 

 

1부터 시작해서 2로 갔다가 막다른길이니 2에서 리턴되면서 그룹의 수를 1 늘려주면 [1-2] 그룹을 찾았다고 할 수 있지 않을까? 그러면 같은 방식으로 3으로 시작했을때, 갈곳이 없으니 그룹의 수를 1 늘려주면 [3] 그룹을 찾아서 총 2개의 네트워크가 있다라고 할 수 있다.

 

이걸 재귀함수로 구현해보자.

 

int dfs(int i, int[][] computers, boolean[] visited)
    {
        //이미 전에 방문했었으면 어떤 그룹에 속해있는 것임.
        if(visited[i])
            return 0;


        for(int j = 0; j< computers.length; ++j)
        {
            //자기자신이 아니고, 연결되어있는 컴퓨터이고, 방문하지 않았다면
            if(i != j && computers[i][j] == 1 && !visited[j])
            {
                //방문했다고 표시
                visited[i] = true;
                //분신에게 일시키기
                dfs(j, computers, visited);

            }
        }

        //더이상 길이 없음
        visited[i] = true;
        return 1;

    }
    public int solution(int n, int[][] computers) {

        int sum = 0;
        boolean[] checked = new boolean[n];
        for(int i =0; i<n; ++i)
        {
            sum += dfs(i, computers, checked);
        }

        return sum;
    }

 

 

먼저 dfs 함수를 보면 for문 안에서 현재 컴퓨터가 연결된 컴퓨터를 찾아 방문했다고 표시하고 있다.

그리고 이것을 분신에게 똑같이 하라고 시킨다. 

분신은 똑같이 하다가 연결된 컴퓨터가 없으면 더이상 길이 없다며 return 1을 한다.

그러면 일을 시켰던 상위분신이 그 결과를 받지만, 딱히 그 결과를 가지고 할일은 없다. 그냥 자신도 return 1을 하고 업무를 끝낸다.

그렇게 재귀함수가 끝나면 solution 함수에서 결과를 받아 sum에 더한다.

이 말은 그룹을 하나 발견했다는 것이다. 그룹을 탐색하면서 그룹 안의 모든 노드에 방문했다는 표시를 했으므로 다시 방문할 일은 없다.

solution의 for문에서 다음 컴퓨터에 대해서 완전히 똑같은 일을 수행하는데, 만약 그 컴퓨터가 이미 방문되있는 컴퓨터이면 즉, 전에 발견했던 그룹안에 있는 컴퓨터면 dfs는 바로 리턴으로 나간다.

 

이런식으로 해서 나온 최종 sum이 답이다.