Algorithm problem-27

1. 문제

• M x N인 문자로 된 배열에 시작점에서 전체에 소문이 퍼지는 시간을 리턴
• 1은 주민이 사는 곳, 0은 x, 하루에 상하좌우 한칸 바로 옆 집으로 퍼짐

2. 시도

• 날짜를 세어줄 카운터를 선언
• 전달받은 시작점을 x로 변경 후 재귀를 시작해야 함
• 재귀를 여기부터 시작
• 베이스 케이스를 설정하자
• 마을을 서치해서 1인 값이 없으면 카운트 리턴
• 리커시브
• 반복문으로 작성해서 모든 x값에 대해 아래의 작업을 진행해야 함
• x지점을 찾아내고, x지점 상하좌우의 값 중 1인 값을 찾고, 1인 값을 x로 변경
• 카운트++
• 종료?
• 시간 내에 풀어내지 못하였음
• 레퍼런스를 보고 이해하기로 하였음

3. 수도코드

const createMatrix = (village) => {//레퍼런스 참조}
const gossipProtocol = function (village, row, col) {
  // 날짜를 세어줄 카운터를 선언
  let cnt = 0;
  // start 지점인 row,col 지점을 x로 변경하고
  village[row] = village[row].substr(0,col) + 'x' + village[row].substr(col+1);
  // 마을에 1이 있는지의 결과값을 저장해줄 변수 선언
  let finder = 1;
  // 매트릭스 내에 1이 있다면 재귀하도록 짜야 함
  while (finder > 0) {
    // 모든 x의 위치를 찾아 값을 저장하고
    let locX = [];
    for (let i = 0; i < village.length; i++) {
      if (village[i].indexOf('x') !== -1) {
        locX.push([i, village[i].indexOf('x')])
      }
    }
    // 저장한 위치의 상하좌우의 값 중 1인 값을 x로 변경시키고
    for (let j = 0; j < locX.length; j++) {
      //상
      if (village[locX[j][0] - 1][locX[j][1]] === 1) {
      }
      //하
      //좌
      //우
    }
    // 카운터++
    // 마을의 요소들이 각각의 문자열로 되어 있어서 반복문으로 각 요소를 검사해서 1이 있는지 확인
    // 이 검사를 while문 끝에서 해줘야 다음 재귀를 할지 안할지를 정하겠지?
    for (let i = 0; i < village.length; i++) {
      finder = finder * village[i].includes('1');
    }
  }
  return cnt;
};

4. 레퍼런스

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) {
  // bfs 구현을 위해 큐를 선언한다.
  // enQueue, deQueue시마다 인덱싱을 다시 하지 않기 위해
  // 순환 큐(circular queue)로 구현한다.
  // queue의 가능한 최대 크기만큼 배열을 선언한다.
  // 문제의 특성에 따라 큐에는 좌표 평면의 한 점이 삽입되고, 한번 삽입된 요소는 두 번 다시 삽입되지 않는다.
  const R = village.length;
  const C = village[0].length;
  const matrix = createMatrix(village);
  const MOVES = [
    [-1, 0], // UP
    [1, 0], // DOWN
    [0, 1], // RIGHT
    [0, -1], // LEFT
  ];
  const MAX_SIZE = R * C; // 가능한 모든 좌표의 크기만큼 큐가 선언되었으므로, 사실 순환큐일 필요는 없다.
  const isValid = (row, col) => row >= 0 && row < R && col >= 0 && col < C;
  const queue = Array(MAX_SIZE);
  let front = 0;
  let rear = 0;
  const isEmpty = (queue) => front === rear;
  const enQueue = (queue, pos) => {
    // 실행 중에 큐가 가득차지는 않기 때문에 별도의 조건문을 작성할 필요가 없다.
    queue[rear] = pos;
    // 모듈러스 연산을 할 필요도 사실 없다.
    rear = (rear + 1) % MAX_SIZE;
  };
  const deQueue = (queue) => {
    const pos = queue[front];
    // 모듈러스 연산을 할 필요도 사실 없다.
    front = (front + 1) % MAX_SIZE;
    return pos;
  };

  let cnt = 0;
  enQueue(queue, [row, col]);
  // 소문이 퍼지는 데 걸리는 시간을 저장한다.
  matrix[row][col] = 0;
  while (isEmpty(queue) === false) {
    // 큐의 가장 앞 자리의 좌표를 얻는다.
    const [row, col] = deQueue(queue);
    cnt = matrix[row][col];

    // 현재 지점을 기준으로 네 방향을 검토한다.
    MOVES.forEach((move) => {
      const [rDiff, cDiff] = move;
      const nextRow = row + rDiff;
      const nextCol = col + cDiff;
      if (isValid(nextRow, nextCol) && matrix[nextRow][nextCol] === '1') {
        enQueue(queue, [nextRow, nextCol]);
        matrix[nextRow][nextCol] = matrix[row][col] + 1;
      }
    });
  }
  return cnt;
};