[JS] 프로그래머스 - 기둥과 보 Another.ver

2020. 11. 1. 20:43ㆍJavascript/알고리즘

문제 설명

빙하가 깨지면서 스노우타운에 떠내려 온 죠르디는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. 죠르디는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.
프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

  • 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

  • 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

단, 바닥은 벽면의 맨 아래 지면을 말합니다.

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.

 

 

예를 들어, 위 그림은 다음 순서에 따라 구조물을 만들었습니다.

  1. (1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.

  2. (2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.

  3. (5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.

  4. (4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.

만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • n은 5 이상 100 이하인 자연수입니다.

  • build_frame의 세로(행) 길이는 1 이상 1,000 이하입니다.

  • build_frame의 가로(열) 길이는 4입니다.

  • build_frame의 원소는 [x, y, a, b]형태입니다.

    • x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.

    • a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.

    • b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.

    • 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.

    • 바닥에 보를 설치 하는 경우는 없습니다.

  • 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.

  • 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.

  • 최종 구조물의 상태는 아래 규칙에 맞춰 return 해주세요.

    • return 하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고있어야 합니다.

    • return 하는 배열의 원소는 [x, y, a] 형식입니다.

    • x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.

    • 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타냅니다.

    • a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.

    • return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해주세요.

    • x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.

 

입출력 예

n build_frame result
5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]
5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]

 

나의 풀이

 이번엔 비트 연산자를 이용한 방법이다. 내 머리에서 나온 것은 아니고 참고자료에 있는 블로그의 코드를 참조했다. 비트 연산자를 이용해서 푸는 방식은 흔한 방식이 아니기 때문에 따로 포스팅을 하고 싶었다. 이 문제에서 설치/제거 해야하는 구조물은 보와 기둥이다. 

 

[그림 1] 약속

 

 보, 기둥을 설치할 때는 몇몇의 조건이 필요하다. 그런데, 조건을 대해 설명하기 전에 우리는 한 가지 약속을 정해야한다. [그림 1]은 16이다(16을 이진수로 바꾸면 10000이다). 우리는 제일 먼저 n*n만큼의 이차원 배열을 만들어줄 것이다. 배열의 이름은 frame으로 문제에서 나온 2차원 벽면을 의미한다. 그리고 frame의 각 원소에 16(10000)으로 초기화 값을 줄 것이다. 즉, 16(10000)은 보, 기둥 둘 다 아무도 설치하지 않은 것을 의미한다. 

 

 

 그럼 다시 본론으로 돌아와서 [그림 1]을 보자. [그림 1]은 우리가 정할 약속을 의미한다. 약속에 대한 설명은 다음과 같다.

  • 10000(16): 기둥, 보 아무것도 설치되지 않은 상태

  • 11000(24): 해당 좌표가 기둥의 시작을 의미

  • 10100(20): 해당 좌표가 기둥의 끝을 의미

  • 10010(18): 해당 좌표가 보의 시작을 의미

  • 10001(17): 해당 좌표가 보의 끝을 의미

  • 11101(29): 해당 좌표가 기둥의 끝, 시작이며 보의 끝을 의미

 

 이해를 돕기 위해 [그림 2]로 예시를 들어보려한다. [그림 2]는 좌표(0,0)에 기둥이, 좌표(0,1)에 보가 이미 설치되어있는 상황을 나타낸다. [그림 2]를 보면 약속의 이진수 코드가 무엇을 의미하는지 확실히 알 수 있을 것이다.

 

[그림 2] 예시 상황

 

이제 조건을 살펴보자.

 

기둥의 설치조건은 다음과 같다.

 

  1. y가 0일 경우

  2. 설치하려는 좌표(x,y)에서 y좌표를 기준으로 아래 방향으로 1만큼 떨어진 곳에 기둥이 설치되있어야 함.

  3. 설치하려는 좌표(x,y)에서 x좌표를 기준으로 왼쪽으로 1만큼 떨어진 곳에 보가 설치되있어야 함.

  4. 설치하려는 좌표(x,y)에 보가 이미 설치되있어야 함.

 즉, 2,3,4는 다음과 같이 풀이할 수 있다.

  • 2번은 좌표(x,y) 값과 4(100)을 AND 계산한 값이 기둥 끝의 의미를 가져야한다.(frame[x][y] & 4).

  • 3,4번은 좌표(x,y) 값과 3(11)을 AND 계산한 값이 보 시작 또는 보 끝의 의미를 가져야한다.frame[x][y] & 3).

 

 이번엔 보의 설치조건을 보자.

 

  1. 설치하려는 좌표(x,y)에서 x좌표를 기준으로 왼쪽으로 1만큼 떨어진 좌표(x-1,y), 오른쪽으로 1만큼 떨어진 좌표(x+1,y) 모두 보가 설치되있어야 함.

  2. 설치하려는 좌표(x,y)에서 y좌표를 기준으로 아래쪽으로 1만큼 떨어진 좌표(x, y-1)에 기둥이 설치되있어야 함.

  3. 설치하려는 좌표(x,y)에서 x좌표를 기준으로 오른쪽을 1만큼, y좌표를 기준으로 아래쪽으로 1만큼 떨어진 좌표(x+1, y-1)에 기둥이 설치되있어야 함.

즉 1, 2, 3은 다음과 같이 풀이할 수 있다.

  • 1번은 좌표(x,y) 값과 1(1)을 AND한 값이 보 끝을 의미하고, 좌표(x+1,y)값과 2(10)을 AND 값이 보 시작을 의미해야한다.

  • 2번은 좌표(x,y) 값과 4(100)을 AND한 값이 기둥 끝을 의미해야한다.

  • 3번은 좌표(x+1,y) 값과 4(100)을 ANd한 값이 기둥 끝을 의미해야한다.

 

 따라서 위 두 조건을 이용하여, 기둥과 보를 설치하면 된다. 하지만 삭제의 경우는 다르다. 기둥의 경우, 삭제할 좌표(x,y)값에 기둥시작을 의미하는 비트를 0으로 만들어줘야 하므로, 7(0111)와 AND 연산을 해줘야하고, 기둥 끝 좌표(x,y+1)에는 11(1011)을 AND 연산을 해줘야한다. 또한, 보의 경우에는 삭제할 좌표(x,y)값에 보 시작을 의미하는 비트를 0으로 만들어줘야 하므로, 13(1101)과 AND 연산을 해줘야하고, 다음 좌표(x+1,y)값에 14(1110)과 AND 연산을 해줘야한다.

 

 

 그 후에는 모든 frame 값(좌표 값)을 두 개의 조건문으로 검사해야한다.

 

  1. 해당 좌표에 기둥 시작을 의미하는 8(1000)비트가 1인가

  2. 해당 좌표에 보 시작을 의미하는 2(0010)비트가 1인가

 만약 1의 경우가 True라면, 기둥의 설치 조건을 검사한다. 단, 모든 설치조건에 부합하지 않아야 삭제를 할 수 있다. 그 반대의 경우 업데이트했던 좌표 값을 다시 복구해주면 된다. 보의 경우도 기둥과 같다. 그리고 최종 값 출력의 경우에는 모든 frame을 검사하여 조건1, 2에 해당되는 값을 배열에 넣어주기만 하면, 자동적으로 오름차순에 따라 요소가 들어가기 때문에 정렬 할 필요가 없다.

 

 

프로그램 코드는 다음과 같다.

const checkCol = (col, y) => (y===0) || (col & 4) || (col & 3);
const checkFloor = (left, right) => ((left & 1) && (right & 2)) || (left & 4) || (right & 4);

const buildCol = (x, y, frame) => {
  const possible = checkCol(frame[x][y], y);
  if(possible){
    frame[x][y] |= 8;
    frame[x][y+1] |= 4;
  }
};

const buildFloor = (x, y, frame) => {
  const possible = checkFloor(frame[x][y], frame[x+1][y]);
  if(possible){
    frame[x][y] |= 2;
    frame[x+1][y] |= 1;
  }
}

const test = (frame) => {
  for(let i=0; i<frame.length; i++){
    for(let j=0; j<frame[i].length; j++){
      if(frame[i][j] & 8)
        if(!checkCol(frame[i][j], j)) return true;
      if(frame[i][j] & 2)
        if(!checkFloor(frame[i][j], frame[i+1][j])) return true;
    }
  }
  return false;
}

const destroyCol = (x, y, frame) => {
  frame[x][y] &= 7;
  frame[x][y+1] &= 11; 

  if(test(frame)){
      frame[x][y] |= 8;
      frame[x][y+1] |= 4; 
  }
};

const destroyFloor = (x, y, frame) => {
  frame[x][y] &= 13;
  frame[x+1][y] &= 14; 

  if(test(frame)){
      frame[x][y] |= 2;
      frame[x+1][y] |= 1; 
  }
};

const getAnswer = (frame, answer) =>{ 
  for(let i=0; i<frame.length; i++){
    for(let j=0; j<frame[0].length; j++){
      if(frame[i][j] & 8)
        answer.push([i, j, 0]);
      if(frame[i][j] & 2)
        answer.push([i, j, 1]);
    }
  }
};

const solution = (n, build_frame) => {
  const frame = Array.from(Array(n+1), () => Array(n+1).fill(16));
  const answer = [];
  // frame: 구조물의 설치 현황 담길 예정

  build_frame.forEach(([x,y,kind,cmd]) => {
    if(kind === 0 && cmd === 0){
      //기둥 삭제
      destroyCol(x, y, frame);
    }
    else if(kind === 0 && cmd === 1){
      //기둥 설치
      buildCol(x, y, frame);
    }
    else if(kind === 1 && cmd === 0){
      //보 삭제
      destroyFloor(x, y, frame);
    }
    else if(kind === 1 && cmd === 1){
      //보 설치
      buildFloor(x, y, frame);
    }
  });

  getAnswer(frame, answer);
  return answer;
};

 

참고 자료

'Javascript > 알고리즘' 카테고리의 다른 글

[JS] 프로그래머스 - 기둥과 보 설치  (0) 2020.11.01
[JS] 프로그래머스 - 멀리뛰기  (0) 2020.10.29
[JS] 프로그래머스 - 거스름 돈  (0) 2020.10.27
[JS] 프로그래머스 - 순위  (0) 2020.10.08
[JS] 프로그래머스 - 베스트 앨범  (0) 2020.10.08

관련글

티스토리툴바