네트워크 — ___을 입력해주세요

728x90

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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이 분포된 영역의 개수를 구하려 했다. 영역의 갯수를 구하면 자연스레 네트워크의 개수도 구해질 것이라 생각해서 구현했다.
테스트 도중 반례를 찾았다. 노드의 개수가 5개 모든 노드가 1을 바라보고 있는 네트워크에선 제대로 작동하지 않았다. 한 시간이 지나도 못 풀자 다른 사람의 풀이를 참고해 풀었다.

우리가 구현할 것은 네트워크 이차원 배열을 보고 각 컴퓨터가 서로 연결돼있는지 판단하는 것이다.

기본 상태이다. 노드 3개, 네트워크 배열 3개, 방문 여부 False

노드 개수만큼 루프를 돌렸을 때 가장 먼저 방문하는 노드는 1번이다. 1번을 방문했을 때 방문 여부를 true로 변경해주고 자기 자신이 아니고 0이 아닌 네트워크 연결점이 있다면 깊이 우선 탐색을 시작한다.

깊이 우선 탐색을 하게되면 2번 노드로 가게 된다. 2번 노드를 방문했기 때문에 방문여부를 true로 변경해주고, 1번과 동일하게 자기자신이 아니면서 0이 아닌 네트워크 연결점을 찾는다. 네트워크 연결점이 있다면 깊이우선 탐색을 시작하는데 1번 노드는 이미 방문했기 때문에 갈 필요 없으므로 1번에서 시작한 깊이 우선 탐색을 끝내고 루프로 돌아간다.

루프 순서대로 2번 노드에 왔지만 이미 방문했으므로 3번 노드로 바로 건너뛴다.

이해를 돕기 위해 그림으로 그렸는데 과정 자체는 간단하다.
총 3 가지로

각 노드가 방문되었는지 확인 -> 방문 안 했다면 방문한다.
방문했다면 방문 여부를 true로 바꾸고 깊이 우선 탐색을 시작한다.
방문이 완료됐으면 answer에 1을 더해준다.

여기서 주의해야 할 점은 노드 방문 이후 깊이 우선 탐색 시 방문 여부를 반드시 판단해야 한다. 그렇지 않으면 무한히 재귀할 수 있다.
이제 코드로 구현해보자.

각 노드가 방문되었는지 확인

fun solution(n: Int, computers: Array<IntArray>): Int {
    var visited = BooleanArray(n)
    var answer = 0

    for (n in computers.indices){
        if(!visited[n]) {
            graph(n, computers, visited)

        }
    }

    return answer
}

노드가 방문되었는지 확인하기 위해 방문 여부를 파악할 수 있는 인스턴스 변수(visited)가 필요하다. 첫 번째로 Boolean타입의 인스턴스 변수를 생성해주고 노드의 개수만큼 길이를 설정해준다.
노드의 갯수만큼 루프를 돌리되 방문하지 않았을 시 깊이 우선 탐색을 시작한다.

방문했다면 방문 여부를 true로 바꾸고 깊이우선탐색을 시작한다.

 //x=루프중인 노드,  visited=방문여부
fun graph(x: Int, computers: Array<IntArray>, visited: BooleanArray) {
    var visited = visited
    //탐색 시작했으면 true
    visited[x] = true
    for (comIdx in computers[x].indices) {
        //자기자신을 호출하지 않고, 1인 노드가 방문이 안되있다면
        if (comIdx != x && computers[x][comIdx] == 1 && !visited[comIdx])
        //재귀 호출
            graph(comIdx, computers, visited)
    }
}

해당 노드의 방문여부를 true로 변경해주고 노드의 배열 개수만큼 반복해준다.
자기 자신이 아니면서 배열의 값이 1, 방문 여부가 false이면 재귀 호출한다.

answer +1 해준다.

fun solution(n: Int, computers: Array<IntArray>): Int {
    var visited = BooleanArray(n)
    var answer = 0

    for (n in computers.indices){
        if(!visited[n]) {
            graph(n, computers, visited)
            answer++
        }
    }

    return answer
}

여기서 하나 재밌는 것이 보일 것이다. 만약 찾지 못했다면 당신은 똑똑한 사람일 것이다.
solution함수에서 graph() 메서드를 호출할 때 graph() 메서드에서 return을 해주지 않았음에도 불구하고 visited의 변경사항이 유지되는 것을 볼 수 있다.
우리는 함수를 호출하고 리턴해줘야 호출한 메서드에서 제대로 된 결괏값을 쓸 수 있다고 배웠다.

참고한 사람의 코드를 보면 dfs() 함수에서 리턴해줬지만 호출 한쪽에선 따로 변수를 통해 할당해주는 모습을 볼 수 없다.

public class Solution {
  public int solution(int n, int[][] computers) {
    int answer = 0;
    boolean[] check = new boolean[n]; // n 갯수만큼 boolean 배열을 만들고 모든 요소를 false로 초기화

    for (int i = 0; i < n; i++) {
      if (!check[i]) {
        dfs(computers, i, check);
        answer++;
      }
    }

    return answer;
  }

  boolean[] dfs(int[][] computers, int i, boolean[] check) {
    check[i] = true;

    for (int j = 0; j < computers.length; j++) {
      if (i != j && computers[i][j] == 1 && check[j] == false) {
        check = dfs(computers, j, check);
      }
    }
    return check;
  }
}

처음에 저것을 보고 지역변수를 패러미터로 넘겨줬는데 왜 재할당을 안 해주지?라고 생각했다. 이 문제로 친구와 얘기했었는데 내가 단단히 오해하고 있었다.
저 변수는 지역변수가 아니라 맨 처음에 말했던 것처럼 인스턴스 변수였던 것이다.!!

나의 단단한 오해를 고치기까지 한 시간이 걸렸지만 오히려 좋았다. 그 이유는 참고한 사람의 코드에서 개선 사항을 발견했기 때문이다.

"왜 재할당을 할 필요 없는가?"부터 설명하자면
자바에서 변수의 종류는 총 3가지이다.

클래스 변수
인스턴스 변수
지역 변수

각 변수별로 특징을 간단히 보자면 클래스 변수는 클래스가 메모리에 적재 시 힙 영역에 적재되고, 인스턴스 변수는 인스턴스 생성 시 힙 영역에 적재된다.
지역 변수는 함수 호출 시 스택 영역에 생성되는 변수이다.
우리가 사용한 배열은 new연산자를 통해 선언했다. new연산자는 클래스 타입의 인스턴스를 생성해주는 역할을 한다. 따라서 우리가 만든 배열은 인스턴스 변수이다.
힙 영역에 사용자가 동적 할당한 인스턴스 변수는 가비지 콜렉터가 버리기 전까지 계속 메모리에 적재되어있다.(중요!)
우리는 패러미터로 배열의 변수명을 넘겼다. 우리가 넘긴 것은 무엇일까?

print(visited)

프린트해보면 이상한 문자열이 나올 것이다. 이 이상한 문자열은 인스턴스의 시작 주소이다. 우리가 넘긴 것은 인스턴스의 시작 주소이고 넘긴 주소를 통해 배열 인스턴스에 접근한다. 배열 인스턴스는 graph() 함수가 종료되어도 힙 영역에 적재돼있기 때문에 따로 리턴하거나 재할당 해줄 필요가 없다.

여기서 var visited = visited를 왜 했느냐고 물어볼 수 있는데 코틀린의 패러미터는 immutable 해서 set이 불가능하다. 우리는 visited [n]를 true로 바꿔줘야 하기 때문에 mutable 한 변수에 할당해서 사용했다

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

    for (int i = 0; i < n; i++) {
      if (!check[i]) {
        dfs(computers, i, check);
        answer++;
      }
    }

    return answer;
  }

  void dfs(int[][] computers, int i, boolean[] check) {
    check[i] = true;

    for (int j = 0; j < computers.length; j++) {
        if (i != j && computers[i][j] == 1 && check[j] == false) {
            check = dfs(computers, j, check);
        }
    }
  }
}

만약 참고한 사람의 코드를 고친다면 이렇게 고칠 수 있다. 리턴할 필요가 없기 때문에 메서드의 리턴 타입은 void가 될 것이고 return check;를 해줄 필요도 없다. 너무 멋지다고 생각한다. 문제 풀면서
분명히 대학교 다니며 배웠는데 머릿속 어딘가에 갇혀 굳어버린 지식을 깰 수 있어서 좋았다.

마지막으로 코드 전문 올리면서 마무리하겠다.

class Solution {
    //n : 노드 갯수, computers : 노드 연결방식
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var visited = BooleanArray(n)
        var answer = 0

        for (n in computers.indices){
            if(!visited[n]) {
                graph(n, computers, visited)
                answer++
            }
        }

        return answer
    }
    //x=루프중인 노드,  visited=방문여부
    fun graph(x: Int, computers: Array<IntArray>, visited: BooleanArray) {
        var visited = visited
        //탐색 시작했으면 true
        visited[x] = true
        for (comIdx in computers[x].indices) {
            //자기자신을 호출하지 않고, 1인 노드가 방문이 안되있다면
            if (comIdx != x && computers[x][comIdx] == 1 && !visited[comIdx])
            //재귀 호출
                graph(comIdx, computers, visited)
        }
    }
}