[Algorithm] Gossip Protocol 알고리즘 문제 Node.js

gossip Protocol이란 전염병 프로토콜로도 불립니다. 특정 지점에서 전염병이 발생 될 경우 전체 매트릭스 구간에 바이러스가 확산되는 방식을 기반으로 한 P2P 통신 프로세스입니다. 분산 시스템에서는 그룹 내 모든 참여자들에게 프로토콜이 전달되도록 Gossip Protocol 알고리즘을 사용합니다. 

 

문제

 

세로,가로 길이가 각각 M,N인 마을이 배열로 주어집니다. '1'은 주민이 살고 있는 좌표를 의미하고, '0'은 주민이 없는 좌표를 의미합니다. 마을에 소문이 퍼지기 시작하면 상하좌우 방향으로 하루에 1칸씩 퍼지게 됩니다. 특정 좌표의 집에서 소문이 시작되어 마을 저체에 소문이 퍼지기 따지 걸리는 시간(day)을 반환하세요.

 

입/출력

 

입력 1 : Village

• string 타입을 요소로 가지는 배열
• village.length = M
• typeof village[i].length = string
• village[i].length = N
• village[i][j] = 세로 i, 가로 j 지점 정보
• village[i][j] = '0' || '1'

 

입력 2 : row

• Number 타입 0이상 정수
• 소문이 시작되는 좌표의 세로 위치값

입력 3 : col

• Number 타입 0이상 정수
• 소문이 시작되는 좌표의 가로 위치값

 

주의사항

 

• M, N <= 100
• row, col에는 항상 주민이 거주하고 있다고 가정합니다.
• 모든 집들은 연결되어 있으며, 한 집에서 다른 집으로 가는 길은 항상 경로가 존재한다고 가정합니다.

 

풀이

 

gossip Protocol을 구현하는 알고리즘 문제입니다. 미로찾기 문제처럼 최종 지점의 좌표값을 구하는 것이 아닌 소문이 확산되는 시간을 구하는 문제이므로, DFS보다는 BFS로 문제를 해결하는 방향이 맞습니다. 

 

village 좌표가 다음과 같이 주어지고 시작 지점이 [1,2]인 경우 마을 전체에 소문이 퍼지는데 걸리는 시간은 3일입니다. 한 좌표에서 상하좌우로 연결된 모든 집을 탐문하면서 마을 전체에 소문이 퍼지는 경로는 아래와 같습니다.

let village = [
  '0101',
  '0111',
  '0110',
  '0100',
];

 

 

 

 

 

입력값으로 0과 1로 구성된 문자열이 주어지므로 먼저 village를 0과 1로 구성된 배열로 변경해주어야 합니다.

const createMatrix = (village) => {
    const matrix = [];
    village.forEach((line) => {
      const row = [];
      for (let i = 0; i < line.length; i++) row.push(line[i]);
      matrix.push(row);
    });
    return matrix;
};

 

주어진 matrix 배열 내에서 BFS를 구현하기 위해서는 방문여부 체크 배열, Queue 배열, 카운팅 배열, 좌표 이동 배열, max값을 저장할 변수, 유효성 검사 함수 등이 필요합니다.

    const matrix = createMatrix(village);
    const M = matrix.length;
    const N = matrix[0].length;

    
	/* BFS 구현시 필요사항 */
    
    // 1. 방문 여부 체크
    const visit = Array(M).fill(0).map(()=>Array(N).fill(false));
    
    // 2. count 생성
    let countArr = Array(M).fill(0).map(()=>Array(N).fill(0));

    // 3. queue 필요
    const queue = [];
    
    // 4. 이동 좌표 필요
    const moveY = [-1,1,0,0];
    const moveX = [0,0,-1,1];

    // 5. max
    let max = 0;
    
    // 6. 유효성 검사 함수 생성
    const isValid = (m, n) =>{

        if(m < 0 || m >= M || n < 0 || n >= N){
            return false;
        }

        return true;
    }

 

최초로 Queue에 소문을 퍼뜨리기 시작한 집의 좌표를 담습니다.

    // 최초 좌표를 queue에 담는다.
    queue.push([row, col]);
    visit[row][col] = true;

 

Queue에서 좌표를 하나씩 출력하면서 마을 전체를 순회합니다. 1이 있는 지점에만 소무이 퍼질 수 있으며 이동 범위는 매트릭스 내로 한정됩니다. 한번 방문한 지점은 다시 방문할 필요는 없습니다. 

while(queue.length > 0){
    const temp = queue.shift();
    const [r, l] = temp;

    for(let i=0; i<4; i++){
        const newRow = r + moveX[i];
        const newCol = l + moveY[i];

        if(isValid(newRow, newCol) && matrix[newRow][newCol]==1 && !visit[newRow][newCol]){
            queue.push([newRow,newCol]);
            visit[newRow][newCol] = true;
            countArr[newRow][newCol] = countArr[r][l] + 1;
        }
    }
}

 

최종적으로 2차원 배열에서 max 값을 구해 출력합니다.

for(let i=0; i<countArr.length; i++){
    for(let j=0; j<countArr[i].length; j++){
        if(countArr[i][j]>max){
            max = countArr[i][j];
        }
    }
}

return max;

 

 

gossip Protocol 소스코드 Node.js

/* 
    @ Author : About-Tech
    @ Algoritm : BFS
    @ Date : 30/06/2022
*/

const createMatrix = (village) => {
    const matrix = [];
    village.forEach((line) => {
      const row = [];
      for (let i = 0; i < line.length; i++) row.push(line[i]);
      matrix.push(row);
    });
    return matrix;
  };
  
  const gossipProtocol = function (village, row, col) {
    // TODO: 여기에 코드를 작성합니다.
    const matrix = createMatrix(village);
    const M = matrix.length;
    const N = matrix[0].length;

    // BFS 로 구현해야 됨

    // 방문 여부 체크
    const visit = Array(M).fill(0).map(()=>Array(N).fill(false));
    // count 생성
    let countArr = Array(M).fill(0).map(()=>Array(N).fill(0));

    // queue 필요
    const queue = [];
    // 이동 좌표 필요
    const moveY = [-1,1,0,0];
    const moveX = [0,0,-1,1];

    // max
    let max = 0;

    // 최초 좌표를 queue에 담는다.
    queue.push([row, col]);
    visit[row][col] = true;

    // 유효성 검사 함수 생성
    const isValid = (m, n) =>{

        if(m < 0 || m >= M || n < 0 || n >= N){
            return false;
        }

        return true;
    }

    

    while(queue.length > 0){
        
        const temp = queue.shift();
        const [r, l] = temp;

        for(let i=0; i<4; i++){
            const newRow = r + moveX[i];
            const newCol = l + moveY[i];

            if(isValid(newRow, newCol) && matrix[newRow][newCol]==1 && !visit[newRow][newCol]){
                queue.push([newRow,newCol]);
                visit[newRow][newCol] = true;
                countArr[newRow][newCol] = countArr[r][l] + 1;
            }
        }
    }
    
    for(let i=0; i<countArr.length; i++){
        for(let j=0; j<countArr[i].length; j++){
            if(countArr[i][j]>max){
                max = countArr[i][j];
            }
        }
    }

    return max;

  };

 

 

 

[Algorithm] 최단거리 알고리즘 문제 Node.js

 

[Algorithm] 기수 정렬 계수 정렬 Node.js

 

[Algorithm] 두 배열에서 k 번째 수 찾기 Javascript(getItemFromTwoSortedArrays 알고리즘)