0. 문제

https://www.codingame.com/ide/puzzle/there-is-no-spoon-episode-1

1. 문제해결을 위해 필요한 개념

배열(array): 많은 데이터를 하나의 변수에 보관하는 용도로 사용하는 자료구조

• 2차원 배열은 표, 행렬, 또는 그리드 형태의 데이터를 저장하는데 적합하다.
• 2차원 배열에서 첫 번째 항목을 x축 또는 y축으로 선언할지는 둘중 편한 방식으로 골라 사용하면 된다. 보통 그래프에서는 x, y좌표의 순서대로 하고, 행렬(matrix)에서는 행(y축)을 기준으로 한다.

2. 문제해결 코드

행렬방식으로 2차원 배열에서 파워노드를 찾는 코드를 만들었다. 오른쪽 파워 노드를 찾는 코드(find_right_power_node)와 아래쪽 파워 노드를 찾는 코드(find_lower_power_node)를 이름 붙은 함수 표현식으로 만들어 '파워 노드 찾기 -> 오른쪽 파워 노드 찾기 -> 아래쪽 파워 노드 찾기'의 순서로 코드가 진행됨을 파악할 수 있도록 한 것이 알고리즘을 짤 때 나 스스로 순서를 헷갈리지 않도록 하는데 도움이 되었다. 오른쪽 파워 노드 찾기가 아래쪽 파워 노드 찾기를 기준 축을 x에서 y축으로 바꾸어 표현한 것이라는 점을 파악하는 것이 또한 알고리즘을 해결하는데 중요한 지점이었다.

const width = parseInt(readline()); // the number of cells on the X axis
const height = parseInt(readline()); // the number of cells on the Y axis
let cell = [];

for (let i = 0; i < height; i++) {
  const line = readline(); // width characters, each either 0 or .
  cell.push(line.split(''));// cell배열에 각 행에 들어갈 문자열을 배열로 바꾸어 넣어준다
}

// 예를 들면 width, height, cell의 모양은 다음과 같다
const width = 4; 
const height = 4;
cell = [
  ['0', '.', '.', '.'],
  ['.', '0', '.', '.'],
  ['.', '.', '0', '.'],
  ['.', '.', '.', '0'],
];

let answer = '';
let power = { x: '', y: '' }; //현재 파워 노드 좌표
let right = { x: '', y: '' }; //현재 파워 노드의 오른쪽 파워 노드 좌표
let lower = { x: '', y: '' }; //현재 파워 노드의 아래쪽 파워 노드 좌표

function find_right_power_node(power_x, power_y) {
  if (power_x + 1 < width) {//x축을 기준으로 현재 파워 노드의 오른쪽에 다음 노드가 있을 때
    for (let r = 0; r < width; r++) {
      if (power_x < r && cell[power_y][r] === '0') {//현재 파워 노드와 같은 y축에 있는 파워노드 중 가장 가까운 노드를 찾는다
        return (right = { x: r, y: power_y });
      } else {
        right = { x: '-1', y: '-1' };
      }
    }
  } else {
    right = { x: '-1', y: '-1' };
  }
}
//오른쪽 파워 노드를 찾는 원리는 같다. 기준 축을 x에서 y로 바꾸어 생각하면 된다.
function find_lower_power_node(power_x, power_y) {
  if (power_y + 1 < height) {
    for (let l = 0; l < height; l++) {
      if (power_y < l && cell[l][power_x] === '0') {
        return (lower = { x: power_x, y: l });
      } else {
        lower = { x: '-1', y: '-1' };
      }
    }
  } else {
    lower = { x: '-1', y: '-1' };
  }
}

for (let y = 0; y < height; y++) {
  for (let x = 0; x < width; x++) {
    if (cell[y][x] === '0') {//현재 파워노드에서 오른쪽 파워 노드와 아래쪽 파워노드를 찾는다 
      power.x = x;
      power.y = y;
      find_right_power_node(power.x, power.y);
      find_lower_power_node(power.x, power.y);

      answer += power.x + ' ' + power.y + ' ' + right.x + ' ' + right.y + ' ' + lower.x + ' ' + lower.y + '\n';
    }
  }
}
console.log(answer);

시간 복잡도 = O(n³)

참고도서:
게임으로 익히는 코딩 알고리즘