Toy 문제 27

문제

세로와 가로의 길이가 각각 M, N인 마을지도가 배열로 주어졌을 때, '1'은 주민이 있는 집을 의미하고 '0'은 주민이 없는 땅을 의미합니다. 이 마을은 소문이 시작되면 하루에 상하좌우 한 칸 바로 옆에 있는 집으로 퍼집니다. 특정 주민의 집 (R, C)으로부터 어떤 소문이 시작될 경우, 마을 전체로 소문이 퍼지는데 걸리는 시간(일)을 리턴해야 합니다.

/*
1. 시작: (1, 2)에서 시작, 소문이 퍼진 곳을 x로 표기
 [
  '0101',
  '01x1',
  '0110',
  '0100',
 ]

2. 1일 뒤
 [
  '0101',
  '0xxx',
  '01x0',
  '0100',
 ]

3. 2일 뒤
 [
  '0x0x',
  '0xxx',
  '0xx0',
  '0100',
 ]

4. 3일 뒤: 소문이 전부 퍼짐 (끝)
 [
  '0x0x',
  '0xxx',
  '0xx0',
  '0x00',
 ]
/*

 

수도코드(해석)

문제의 핵심은 어떠한 말판(2중 배열)에서 0과 1만 존재하는데, 1이 x로 변경이 하루에 한번 확장이 되어 그 시간을 구하라는 뜻 입니다.

앞선 26번문제랑 비슷하지만 조금 다릅니다. 26번에서는 BFS만 사용을 하였지만 이번 문제에서는 Queue와 더불어 같이 사용 합니다. 그래서 일정 정도는 코드가 비슷하지만 더 추가된 부분이 존재 하는 것 입니다.

 

앞선 문제에서는 상하좌우 동시에 출발을 할 필요성이 없고 이번문제에서는 1을 모두 x로 뒤덮는 과정이기 때문에 상하좌우가 동시에 출발이 가능해야 합니다.

그래서 상하좌우 좌표가 이동된 코드를 Queue 변수에넣고 +1하여 (꼭 x로 뒤덮을 필요가 없기 때문에 +1을 해주어 시간으로 계산) 시간을 계산시켜 줍니다. 상하좌우가 무조건 항상 이동된다고 생각했을 때, 큐스텍의 길이를 생각하면 처음에는 4, 두 번째 12로 될 것입니다.(전 출발방향 경우의 수 4 제외)

 

문제의 풀이방법은 26번 문제를 이해하면 27번 문제도 쉽게 이해했지만 워낙 구현이 긴 코드라 다시 풀어보는 연습을 해야하지만, 복습하고 다시 푸는게 참 귀찮고 어려운 부분인 것 같습니다 ㅠㅠ

 

코드(Reference)

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 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;
};