[프로그래머스] 네트워크

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

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

코딩테스트 고득점 Kit - DFS/BFS

LEVEL 3

문제설명

컴퓨터의 개수 n, 컴퓨터간 연결 정보를 담은 2차원 배열 computers가 주어졌을 때, 네트워크 개수를 구하는 solution 함수를 작성하시오.

• 컴퓨터 A와 컴퓨터 B가 연결되어 있고, 컴퓨터 B와 컴퓨터 C가 연결되어 있다면 컴퓨터 A와 컴퓨터 C도 간접적올 연결되어 있다고 볼 수 있다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크에 상에 있다.

INPUT

n

• 컴퓨터의 개수
• 1 ≤ n ≤ 200

computers

• 2차원 배열
• 각 컴퓨터는 0부터 n-1인 정수로 표현
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]와 computers[j][i]는 1로 표현 (연결되어 있지 않으면 0)
• computer[i][i]는 항상 1

OUTPUT

• 네트워크 개수 (양의 정수)

나의 풀이

0번 컴퓨터에서부터 시작하여 n-1번 컴퓨터까지 모든 노드를 완전탐색한다.

• BFS - Queue
  1. 전체 네트워크 개수를 담을 answer 변수를 선언하고 1을 할당한다. (1은 탐색을 시작할 0번 컴퓨터에서 시작하는 네트워크를 의미한다)
  2. 다음으로 방문할 노드들을 담을 queue와 각 노드들을 방문했는지 여부를 boolean으로 담을 배열 visited를 생성한다. queue에는 첫 탐색 지점으로 0(0번 컴퓨터)을 넣는다.
  3. queue에 다음으로 방문할 노드가 남아있는 동안 while문으로 계속 다음 노드를 탐색한다.
     1. queue의 가장 앞에 있는 노드(현재 방문할 노드)를 shift하여 꺼낸뒤 current 변수에 저장한다 .
     2. current 노드를 방문했음을 visited 배열에 표시한다.
     3. current 노드에 연결된 노드들 중 아직 방문하지 않은 노드들을 queue에 push한다.
     4. queue가 비어 더 이상 방문할 이어진 노드가 없는 경우, 하나의 네트워크가 끝난 것을 의미한다. 따라서 answer 값에 1을 더한 후 visited에서 아직 방문하지 않은 노드를 찾아 queue에 추가하여 새로운 네트워크 탐색을 시작한다.
  4. 전체 네트워크 개수가 담긴 answer를 return한다.

// BFS - queue
function solution(n, computers) {
  // 1. 전체 네트워크 개수를 담을 answer 변수를 선언하고 1을 할당한다
  let answer = 1;
  // 2. 다음으로 방문할 노드들을 담을 queue와 각 노드들의 방문 여부를 담을 배열 visited를 생성한다
  const queue = [0]; // 0번 컴퓨터부터 탐색 시작
  const visited = new Array(n).fill(false);
  // 3. queue에 다음으로 방문할 노드가 남아있는 동안 while문으로 계속 다음 노드를 탐색한다
  while (queue.length !== 0) {
    // 3-1. queue의 가장 앞에 있는 노드를 shift로 꺼낸 뒤 current 변수에 저장한다
    const current = queue.shift();
    // 3-2. current 노드를 방문했음을 visited에 표시한다
    visited[current] = true;
    // 3-3. current 노드에 연결된 노드들 중 아직 방문하지 않은 노드들을 queue에 push한다
    for (let i = 0; i < n; i++) {
      if (computers[current][i] === 1 
          && i !== current
          && !visited[i]) {
      	queue.push(i);
      }
    }
    // 3-4. queue가 비어 더 이상 방문할 이어진 노드가 없는 경우, 
    //	    answer값에 1을 더한 후 visited에서 아직 방문하지 않은 노드를 찾아 stack에 추가한다
    if (queue.length === 0) {
      const unvisited = visited.indexOf(false);
      if (unvisited !== -1) {
        answer++;
        queue.push(unvisited);
      }
    }
  }
  // 4. 전체 네트워크 개수가 담긴 answer를 return한다
  return answer
}

• DFS - Stack
  1. 전체 네트워크 개수를 담을 answer 변수를 선언하고 1을 할당한다. (1은 탐색을 시작할 0번 컴퓨터에서 시작하는 네트워크를 의미한다)
  2. 다음으로 방문할 노드들을 담을 stack과 각 노드들을 방문했는지 여부를 boolean으로 담을 배열 visited를 생성한다. stack 에는 첫 탐색 지점으로 0(0번 컴퓨터)을 넣는다.
  3. stack에 다음으로 방문할 노드가 남아있는 동안 while문으로 계속 다음 노드를 탐색한다.
     1. stack의 가장 마지막에 있는 노드(현재 방문할 노드)를 pop하여 꺼낸 뒤 current 변수에 저장한다.
     2. current 노드를 방문했음을 visited 배열에 표시한다.
     3. current 노드에 연결된 노드들 중 아직 방문하지 않은 노드들을 stack에 push한다.
     4. stack이 비어 더 이상 방문할 이어진 노드가 없는 경우, 하나의 네트워크가 끝난 것을 의미한다. 따라서 answer 값에 1을 더한 후 visited에서 아직 방문하지 않은 노드를 찾아 stack에 추가하여 새로운 네트워크 탐색을 시작한다.
  4. 전체 네트워크 개수가 담긴 answer를 return한다.

// DFS - stack
function solution(n, computers) {
  // 1. 전체 네트워크 개수를 담을 answer 변수를 선언하고 1을 할당한다
  let answer = 1;
  // 2. 다음으로 방문할 노드들을 담을 stack과 각 노드들의 방문 여부를 담을 배열 visited를 생성한다
  const stack = [0]; // 0번 컴퓨터부터 탐색 시작
  const visited = new Array(n).fill(false);
  // 3. stack에 다음으로 방문할 노드가 남아있는 동안 while문으로 계속 다음 노드를 탐색한다
  while (stack.length !== 0) {
    // 3-1. stack의 가장 마지막 노드를 pop으로 꺼낸 뒤 current 변수에 저장한다
    const current = stack.pop();
    // 3-2. current 노드를 방문했음을 visited에 표시한다
    visited[current] = true;
    // 3-3. current 노드에 연결된 노드들 중 아직 방문하지 않은 노드들을 stack에 push한다
    for (let i = 0; i < n; i++) {
      if (computers[current][i] === 1 
          && i !== current
          && !visited[i]) {
      	stack.push(i);
      }
    }
    // 3-4. stack이 비어 더 이상 방문할 이어진 노드가 없는 경우, 
    //	    answer값에 1을 더한 후 visited에서 아직 방문하지 않은 노드를 찾아 stack에 추가한다
    if (stack.length === 0) {
      const unvisited = visited.indexOf(false);
      if (unvisited !== -1) {
        answer++;
        stack.push(unvisited);
      }
    }
  }
  // 4. 전체 네트워크 개수가 담긴 answer를 return한다
  return answer
}

• DFS - Recursion
  1. 전체 네트워크 개수를 담을 answer 변수를 선언하고 n을 할당한다. (즉, 모든 노드가 연결되지 않고 각각의 네트워크를 형성하고 있을 경우를 default로 둔다)
  2. 각 노드들을 방문했는지 여부를 boolean으로 담을 배열 visited를 생성한다.
  3. 재귀함수 dfs를 선언한다. 인자로는 현재 방문하고 있는 노드, current를 받는다.
     1. 만약 current가 이미 방문한 노드라면 다른 노드에 연결되었다는 뜻이므로 answer 값에 1을 뺀 후 탐색하지 않는다. (= return한다)
     2. 만약 current가 아직 방문하지 않은 노드라면, 방문했음을 visited 배열에 표시한다.
     3. current 노드에 연결된 노드들 중 아직 방문하지 않은 노드들을 dfs로 탐색한다.
  4. 0번 컴퓨터부터 n-1번 컴퓨터까지 dfs로 탐색한다.
  5. 전체 네트워크 개수가 담긴 answer를 return한다.

// DFS - recursion
function solution(n, computers) {
  // 1. 전체 네트워크 개수를 담을 answer 변수를 선언하고 n을 할당한다
  let answer = n;
  // 2. 각 노드들의 방문 여부를 담을 배열 visited를 생성한다
  const visited = new Array(n).fill(false);
  // 3. 재귀함수 dfs를 선언하고 인자로는 현재 방문하고 있는 노드 current를 받는다
  function dfs(current) {
    // 3-1. 만약 current가 이미 방문한 노드라면 answer 값에 1을 뺀 후 return한다
    if (visited[current]) {
      answer--;
      return;
    }
    // 3-2. 만약 current가 아직 방문하지 않은 노드라면 방문했음을 visited에 표시한다
    visited[current] = true;
    // 3-3. current에 연결된 노드들 중 아직 방문하지 않은 노드들을 dfs로 탐색한다
    for (let i = 0; i < n; i++) {
      if (computers[current][i] === 1 
          && i !== current 
          && !visited[i]) {
        dfs(i);
      }
    }
  }
  // 4. 0번 컴퓨터부터 n-1번 컴퓨터까지 dfs로 탐색한다
  for (let i = 0; i < n; i++) {
    dfs(i);
  }
  // 5. 전체 네트워크 개수가 담긴 answer를 return한다
  return answer;
}

BFS, DFS 구현을 연습해보기에 좋은 문제였다.