[프로그래머스] 네트워크 (TypeScript로 풀기)

문제 설명

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

아래와 같이 2개의 네트워크가 있습니다.

예제 1 예시

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

예제 2 예시

---

문제 풀이

문제분류가 DFS였습니다. 거기서 힌트를 받아 DFS를 예전에 구현할 때 DFS메서드를 만들었던 기억이 있어 시도하였지만 한참 이전에 했던 것이라 떠오르지 않아 반복문을 사용하여 문제 해결을 먼저 하자고 생각하여 반복에 반복에 반복을 통하여 구현을 먼저 하였습니다.

첫 for문의 경우는 2차 배열 중 한 행씩 반복하도록 하였습니다.

그 행을 반복시켰는지 확인하기 위하여 if(computers [i][i])는 방문한 적 있는 컴퓨터인가 확인하여 방문한 적이 없다면 방문을 확인하기 위하여 (i, i)의 요소를 0으로 바꾸어 computers [i][i]가 0이라면 이미 실행하였기 때문에 answer을 증가시키지 않습니다. 1이라면 i값을 stackArr에 넣어줍니다.

while문을 통하여 stackArr에 값이 없을 때까지 반복을 하며 연결되어 있는 컴퓨터를 확인하고자 하였습니다. 연결된 컴퓨터를 확인하며 연결된 컴퓨터의 번호를 stackArr에 넣어줍니다. 이 과정을 반복하며 연결된 컴퓨터가 더 이상 없다면 while문을 빠져나와 가장 밖의 for문의 반복이 시작됩니다.

function solution(n: number, computers: number[][]) {
  let answer: number = 0;
  let stackArr: number[] = [];
  for (let i = 0; i < n; i++) {
    if (computers[i][i]) {
      computers[i][i] = 0;
      answer++;
      stackArr.push(i);
    }
    while (stackArr.length) {
      let num: number = stackArr.pop();
      for (let j = 0; j < n; j++) {
        if (num == j) {
          computers[num][num] = 0;
          continue;
        }
        if (computers[num][j] == 1) {
          computers[num][j] = 0;
          computers[j][num] = 0;
          stackArr.push(j);
        }
      }
    }
  }
  return answer;
}

위의 방법으로 해결 후 DFS를 다시 공부하고자 찾아보고 방문한 것을 또 다른 배열을 통하여 확인하는 것을 보고 코딩을 하였습니다. check라는 배열을 이용하여 방문한 적이 있는지 확인하기 위하여 초기값을 false로 채웠습니다.

위의 방식과 마찬가지로 방문을 한 컴퓨터의 번호에 해당하는 check배열의 index의 값을 true로 변경하였습니다. 그러면서 DFS함수를 실행합니다.

DFS의 함수 안에 for문은 computers의 이차배열에 각 행을 검사합니다. 

if(num!= j && arr [num][j] == 1 && check [j] == false)의 조건은 num!=j는 연결이 되었는지 확인하는 컴퓨터가 자기 자신이 아닌지 확인합니다. arr [num][j] == 1은 num번째 컴퓨터가 j번째 컴퓨터와 연결이 되었는지 확인합니다. check [j] == false은 j번째 컴퓨터에 방문한 적이 있는지 확인합니다.

따라서 자기 자신이 아니면서 j번째 컴퓨터와 연결되어 있으면서 j번째 컴퓨터를 확인한 적이 없다면 DFS함수를 재귀적함수로 실행합니다.

이러 한식으로 연결된 컴퓨터들을 반복적으로 확인을 하고 확인할 컴퓨터가 없다면 solution함수의 for문이 다음 i를 검사합니다. 이렇게 반복하여 결과를 확인하는 방법이 있습니다.

function solution(n: number, computers: number[][]): number {
  let answer: number = 0;
  let check: boolean[] = [];
  for (let i = 0; i < n; i++) {
    check.push(false);
  }
  for (let i = 0; i < n; i++) {
    if (!check[i]) {
      DFS(computers, i, check);
      answer++;
    }
  }
  return answer;
}
function DFS(arr: number[][], num: number, check: boolean[]): boolean[] {
  check[num] = true;

  for (let j = 0; j < arr.length; j++) {
    if (num != j && arr[num][j] == 1 && check[j] == false) {
      check = DFS(arr, j, check);
    }
  }
  return check;
}