Node.js)백준 15684번: 사다리 조작

 

 

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

사다리 3개까지 그려보고 안되면 종료하라고 해서 그냥 for문으로 접근ㅋ (통과는 했는데 시간 오래 걸림)

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");

const [N, M, H] = input.shift().split(' ').map(Number);

let sadari = Array.from(Array(H), () => Array(N - 1).fill(false));
if (input.length > 0) {
  input.map(v => v.split(' ').map(Number)).forEach(v => {
    const [x, y] = v;
    sadari[x - 1][y - 1] = true;
  });
}



function checkSadari() {
  let success = true;
  for (let i = 0; i < N; i++) {
    let now = i;
    let cnt = 0;
    while (cnt < H) {
      if (now < N - 1 && sadari[cnt][now]) {
        now = now + 1;
      } else if (now > 0 && sadari[cnt][now - 1]) {
        now = now - 1;
      }
      cnt++
    }
    if (now != i) {
      success = false;
      break;
    }
  }
  if (success) return true;
  return false;
}

function canDraw(x, y) {
  if (sadari[x][y]) return false;
  if (y > 0 && sadari[x][y - 1]) return false;
  if (y < N - 2 && sadari[x][y + 1]) return false;
  return true;
}

function main() {
  // 아무것도 안 그리고 체크
  if (checkSadari()) {
    return 0;
  }

  //하나그리고 체크
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < N - 1; j++) {
      if (canDraw(i, j)) {
        sadari[i][j] = true;
        if (checkSadari()) {
          return 1;
        } else {
          sadari[i][j] = false;
        }
      }
    }
  }

  // 두개그리고 체크
  for (let a = 0; a < H; a++) {
    for (let b = 0; b < N - 1; b++) {
      for (let c = 0; c < H; c++) {
        for (let d = 0; d < N - 1; d++) {
          if ((a != c || (a == c && Math.abs(b - d) > 1)) && canDraw(a, b) && canDraw(c, d)) {
            sadari[a][b] = true;
            sadari[c][d] = true;
            if (checkSadari()) {
              return 2;
            } else {
              sadari[a][b] = false;
              sadari[c][d] = false;
            }
          }
        }
      }
    }
  }


  // 세개 그리고 체크
  for (let a = 0; a < H; a++) {
    for (let b = 0; b < N - 1; b++) {
      for (let c = 0; c < H; c++) {
        for (let d = 0; d < N - 1; d++) {
          for (let e = 0; e < H; e++) {
            for (let f = 0; f < N - 1; f++) {
              if ((a != c || (a == c && Math.abs(b - d) > 1))
                && (a != e || (a == e && Math.abs(b - f) > 1))
                && (e != c || (e == c && Math.abs(f - d) > 1))
                && canDraw(a, b) && canDraw(c, d) && canDraw(e, f)) {
                sadari[a][b] = true;
                sadari[c][d] = true;
                sadari[e][f] = true;
                if (checkSadari()) {
                  return 3;
                } else {
                  sadari[a][b] = false;
                  sadari[c][d] = false;
                  sadari[e][f] = false;
                }
              }
            }
          }
        }
      }
    }
  }

  // 실패.
  return -1;
}





console.log(main());

 

 

 

 

 

다른 분들이 푼 거 참고해서 좀 수정

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");

const [N, M, H] = input.shift().split(' ').map(Number);

let sadari = Array.from(Array(H), () => Array(N - 1).fill(false));
if (input.length > 0) {
  input.map(v => v.split(' ').map(Number)).forEach(v => {
    const [x, y] = v;
    sadari[x - 1][y - 1] = true;
  });
}



function checkSadari() {
  let success = true;
  for (let i = 0; i < N; i++) {
    let now = i;
    let cnt = 0;
    while (cnt < H) {
      if (now < N - 1 && sadari[cnt][now]) {
        now = now + 1;
      } else if (now > 0 && sadari[cnt][now - 1]) {
        now = now - 1;
      }
      cnt++
    }
    if (now != i) {
      success = false;
      break;
    }
  }
  if (success) return true;
  return false;
}

function canDraw(x, y) {
  if (sadari[x][y]) return false;
  if (y > 0 && sadari[x][y - 1]) return false;
  if (y < N - 2 && sadari[x][y + 1]) return false;
  return true;
}

function drawSadari(cnt, end, last) {
  if (cnt == end) {
    if (checkSadari()) {
      return process.exit(console.log(end));
    }
  } else {
    for (let i = last; i < H * N; i++) {
      const x = Math.floor(i / N);
      const y = i % N;
      if (canDraw(x, y)) {
        sadari[x][y] = true;
        drawSadari(cnt + 1, end, i + 2);
        sadari[x][y] = false;
      }
    }
  }
}


function main() {
  for (let i = 0; i <= 3; i++) {
    drawSadari(0, i, 0)
  }
  return console.log(-1);
}

main();