프로그래머스-카카오: 기둥과 보(Javascript)

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/60061

문제

문제 제한사항은 링크에서 확인

문제를 해결한 방법

같은 지점에 기둥과 보가 동시에 존재하는 경우도 있기 때문에 3차원 배열을 사용했습니다.

• floor[0][x][y] - 좌표 x,y에 기둥이 있으면 true, 없으면 false
• floor[1][x][y] - 좌표 x,y에 보가 있으면 true, 없으면 false

설치하는 경우

• 기둥 - validColumns() 함수를 이용하여 해당 좌표에서 기둥을 설치할 수 있는지 확인

  function validColumns(floor, x, y) {
    if (y === 0) { // 바닥인 경우
      return true;
    } else if (floor[0][x][y - 1]) { // 밑에 기둥이 있는 경우
      return true
    } else if (x > 0 && floor[1][x - 1][y]) { // 왼쪽에 보가 있는 경우
      return true;
    } else if (floor[1][x][y]) { // 보 위에 있는 경우
      return true;
    }
    return false;
  }
  

  1. 바닥인 경우
  2. 밑에 기둥이 있는 경우
  3. 왼쪽에 보가 있는 경우
  4. 기둥이 보 바로 위에 있는 경우

• 보 - validBeams() 함수를 이용하여 해당 좌표에 보를 설치할 수 있는지 확인

  function validBeams(floor, n, x, y) {
    // 기둥 위에 있는 경우
    if (floor[0][x][y - 1]) { 
      return true;
    }
    // 우측 아래 기둥이 있는 경우
    else if (x < n && floor[0][x + 1][y - 1]) { 
      return true;
    } 
    // 양 옆에 보가 있는 경우
    else if (x > 0 && x < n && floor[1][x - 1][y] && floor[1][x + 1][y]) { 
      return true;
    }
    
    return false;
  }
  

  1. 바로 밑에 기둥이 있는 경우
  2. 우측 아래에 기둥이 있는 경우
  3. 양 옆에 보가 있는 경우

삭제하는 경우

• 기둥 - 해당 위치에 기둥을 제거하고 주변 구조물이 설치 가능한지 검사

  function removeColumns(floor, n, x, y) {
    floor[0][x][y] = false; // 일단 기둥을 제거하고 주변 구조물 유효성 검사
        
    // 위에 기둥이 있는 경우
    if (y < n && floor[0][x][y + 1] && !validColumns(floor, x, y + 1)) { 
      floor[0][x][y] = true;
    } 
    // 위에 보가 있는 경우
    else if (y < n && floor[1][x][y + 1] && !validBeams(floor, n, x, y + 1)) { 
      floor[0][x][y] = true;
    }
    // 좌측 위에 보가 있는 경우
    else if (x > 0 && floor[1][x - 1][y + 1] && !validBeams(floor, n, x - 1, y + 1)) { 
      floor[0][x][y] = true;
    }
  }
  

  1. 위에 기둥이 존재한다면 validColumns()으로 확인
  2. 위에 보가 존재한다면 validBeams()으로 확인
  3. 좌측 대각선 위에 보가 존재하면 validBeams()으로 확인
  4. 모든 조건을 통과한다면 제거

• 보 - 해당 위치에 보를 제거하고 주변 구조물이 설치 가능한지 검사

  function removeBeams(floor, n, x, y) {
    floor[1][x][y] = false; // 일단 보를 제거하고 주변 구조물 유효성 검사
        
    // 현재 위치에 기둥이 존재하는 경우
    if (floor[0][x][y] && !validColumns(floor, x, y)) { 
      floor[1][x][y] = true;
    } 
    // 우측에 기둥이 존재하는 경우  
    else if (x < n && floor[0][x + 1][y] && !validColumns(floor, x + 1, y)) { 
      floor[1][x][y] = true;
    } 
    // 양 옆에 보가 존재하는 경우 
    else if (x > 0 && x < n && floor[1][x - 1][y] && floor[1][x + 1][y]) {
      // 둘 중에 하나라도 안되면 true
      if (!validBeams(floor, n, x - 1, y) || !validBeams(floor, n, x + 1, y)) { 
        floor[1][x][y] = true;
      }
    } 
    // 우측에만 보가 존재하는 경우
    else if (x < n && floor[1][x + 1][y] && !validBeams(floor, n, x + 1, y)) { 
      floor[1][x][y] = true;
    } 
    // 좌측에만 보가 존재하는 경우
    else if (x > 0 && floor[1][x - 1][y] && !validBeams(floor, n, x - 1, y)) { 
      floor[1][x][y] = true;
    }
  }
  

  1. 현재 위치에 기둥이 존재한다면 validColumns()으로 확인
  2. 우측에 기둥이 존재한다면 validColumns()으로 확인
  3. 양옆에 보가 존재한다면 양쪽에 validBeams()으로 확인
  4. 우측에만 보가 존재한다면 validBeams()으로 확인
  5. 좌측에만 보가 존재한다면 validBeams()으로 확인
  6. 모든 조건을 통과한다면 제거

소스 코드 (Javascript)

function validColumns(floor, x, y) {
  if (y === 0) { // 바닥인 경우
    return true;
  } else if (floor[0][x][y - 1]) { // 밑에 기둥이 있는 경우
    return true
  } else if (x > 0 && floor[1][x - 1][y]) { // 왼쪽에 보가 있는 경우
    return true;
  } else if (floor[1][x][y]) { // 보 위에 있는 경우
    return true;
  }
  return false;
}

function validBeams(floor, n, x, y) {
  // 기둥 위에 있는 경우
  if (floor[0][x][y - 1]) { 
    return true;
  }
  // 우측 아래 기둥이 있는 경우
  else if (x < n && floor[0][x + 1][y - 1]) { 
    return true;
  } 
  // 양 옆에 보가 있는 경우
  else if (x > 0 && x < n && floor[1][x - 1][y] && floor[1][x + 1][y]) { 
    return true;
  }

  return false;
}

function removeColumns(floor, n, x, y) {
  floor[0][x][y] = false; // 일단 기둥을 제거하고 주변 구조물 유효성 검사
    
  // 위에 기둥이 있는 경우
  if (y < n && floor[0][x][y + 1] && !validColumns(floor, x, y + 1)) { 
    floor[0][x][y] = true;
  } 
  // 위에 보가 있는 경우
  else if (y < n && floor[1][x][y + 1] && !validBeams(floor, n, x, y + 1)) { 
    floor[0][x][y] = true;
  }
  // 좌측 위에 보가 있는 경우
  else if (x > 0 && floor[1][x - 1][y + 1] && !validBeams(floor, n, x - 1, y + 1)) { 
    floor[0][x][y] = true;
  }
}

function removeBeams(floor, n, x, y) {
  floor[1][x][y] = false; // 일단 보를 제거하고 주변 구조물 유효성 검사
    
  // 현재 위치에 기둥이 존재하는 경우
  if (floor[0][x][y] && !validColumns(floor, x, y)) { 
    floor[1][x][y] = true;
  } 
  // 우측에 기둥이 존재하는 경우  
  else if (x < n && floor[0][x + 1][y] && !validColumns(floor, x + 1, y)) { 
    floor[1][x][y] = true;
  } 
  // 양 옆에 보가 존재하는 경우 
  else if (x > 0 && x < n && floor[1][x - 1][y] && floor[1][x + 1][y]) {
    // 둘 중에 하나라도 안되면 true
    if (!validBeams(floor, n, x - 1, y) || !validBeams(floor, n, x + 1, y)) { 
      floor[1][x][y] = true;
    }
  } 
  // 우측에만 보가 존재하는 경우
  else if (x < n && floor[1][x + 1][y] && !validBeams(floor, n, x + 1, y)) { 
    floor[1][x][y] = true;
  } 
  // 좌측에만 보가 존재하는 경우
  else if (x > 0 && floor[1][x - 1][y] && !validBeams(floor, n, x - 1, y)) { 
    floor[1][x][y] = true;
  }
}



function solution(n, build_frame) {
  const answer = [];
  const floor = new Array(2).fill(0).map(v => new Array(n + 1));
  for (let i = 0; i <= n; i++) {
    floor[0][i] = new Array(n + 1);
    floor[1][i] = new Array(n + 1);
  }

  for (let i = 0; i < build_frame.length; i++) {
    const [x, y, a, b] = build_frame[i];
    if (b === 1) {
      if (a === 0) {
        if (validColumns(floor, x, y)) {
          floor[0][x][y] = true;
        }
      } else {
        if (validBeams(floor, n, x, y)) {
          floor[1][x][y] = true;
        }
      }
    } else {
      if (a === 0) {
        removeColumns(floor, n, x, y);
      } else {
        removeBeams(floor, n, x, y);
      }
    }
  }

  for (let i = 0; i < 2; i++) {
    for (let x = 0; x <= n; x++) {
      for (let y = 0; y <= n; y++) {
        if (floor[i][x][y]) {
          answer.push([x, y, i]);
        }
      }
    }
  }

  // 출력 조건에 맞게 정렬
  answer.sort((a, b) => {
    if (a[0] === b[0]) {
      if (a[1] === b[1]) {
        return a[0] - b[0];
      }
      return a[1] - b[1];
    }
    return a[0] - b[0];
  })

  return answer;
}