백준 2239번 정사각형의 개수 자바스크립트

 

진짜 막막하긴 한데 한 줄씩 체크하면서 뭔가 정렬 알고리즘을 통해 최적을 선택하면 될거같다.     

 

103000509

 

2, 4, 6, 7, 8

첫번째 자리 2, 4, 7, 8

네번째자리 4

다섯번째 자리 6, 7, 8

여덟번째 자리 2, 4, 6, 7, 8

 

각각 가능한 수를 구해서 재귀를 이용하면 될거같다. 

function isValidRow (array) {
   const removeZeroArray = array.filter(num => num !== 0);
  const set_array = new Set(removeZeroArray);
  if (removeZeroArray.length === set_array.size) {
    return true
  }
  return false
}


console.log(isValidRow([1, 2, 3]))

 

가로 한 줄은 체크할 수 있는데 그중 한 자리에서 그대로 내려오는 걸 진행하려면 2차원 배열이 필요하다.

접근을 너무 사람으로 했다..

---

하다보니 함수로 역할을 나눠야해서, 그때그때 만들어서 수정하다보니 해결되었다. 

function change2DArray(input) {
  return input.split('\n').map(row => row.split('').map(Number));
}

const input = `103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107`;

console.log(change2DArray(input));

 

\n을 기준으로 나눠서 배열로 만들고 각 요소를 다시 쪼개면서 숫자로 변형한다.

function isValid(x, y, number, array) {
  for (let i = 0; i < 9; i++) {
    if (i !== y && array[x][i] === number) return false;
    if (i !== x && array[i][y] === number) return false;
  }
 
  const startRow = Math.floor(x / 3) * 3;
  const startCol = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if ((startRow + i !== x || startCol + j !== y) && array[startRow + i][startCol + j] === number) {
        return false;
      }
    }
  }

  return true;
}

 

일단 특정 좌표를 선택하고(array, x, y) 특정 숫자와 비교해야한다. 먼저 row를 비교하면서 특정 좌표와 중복되는 지점을 제외하고 해당 row에 특정 숫자가 있는 경우 유효하지 않음을 반환한다. col 역시 마찬가지로 비교한다.

 

이후, 현재 좌표를 기준으로 3X3 사각형을 구해 해당 숫자가 사각형 안에서 유효한지 검사한다.

function checkArray(array) {
  for (let rowIndex = 0; rowIndex < 9; rowIndex++){
    for (let colIndex = 0; colIndex < 9; colIndex++){
      if (array[rowIndex][colIndex] === 0) {
        for (let num = 1; num <= 9; num++) {
          if(isValid(rowIndex, colIndex, num, array)){
            array[rowIndex][colIndex] = num;
            // 나머지도 검사했는데, 유효하면 최종 정답
            // 나머지에서 에러나면 0으로 다시 바꾸고 다음 0을 검사
            if (checkArray(array)){
              return true;
            } else {
               array[rowIndex][colIndex] = 0;
            }
          }
        }
        return false;
      }
    }
  }
  return true;
}

 

2차원 배열이 주어졌을때 처음부터 끝까지 검사하면서 0인 좌표에서 멈춰서 해당 숫자인 경우 유효한지 검사한다. 유효한 숫자인경우, 다음 0인 좌표에서 같은 검사를 다시 반복하여 특정숫자 계속해서 유효한지 판단하고, 아니면 다시 0으로 변경한 후 다음 숫자를 넣어보며 반복한다.   

'143628579' '572139468' '680754213' '318542796' '260917350' '750863024' '025471630' '039205840' '804396107'

 

처음에는 특정 좌표가 0이 아닌 경우에 처리를 안해줘서 0이 유지되었는데, 0이 아닌경우 false를 반환하여 재귀할 때 안쪽 if (checkArray(array)의 else로 잡혀서 0으로 만들고 다시 반복해줘야했다.

최종 답안

function change2DArray(input) {
  return input.split('\n').map(row => row.split('').map(Number));
}

function isValid(x, y, number, array) {
  for (let i = 0; i < 9; i++) {
    if (i !== y && array[x][i] === number) return false;
    if (i !== x && array[i][y] === number) return false;
  }
 
  const startRow = Math.floor(x / 3) * 3;
  const startCol = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if ((startRow + i !== x || startCol + j !== y) && array[startRow + i][startCol + j] === number) {
        return false;
      }
    }
  }

  return true;
}

function checkArray(array) {
  for (let rowIndex = 0; rowIndex < 9; rowIndex++){
    for (let colIndex = 0; colIndex < 9; colIndex++){
      if (array[rowIndex][colIndex] === 0) {
        for (let num = 1; num <= 9; num++) {
          if(isValid(rowIndex, colIndex, num, array)){
            array[rowIndex][colIndex] = num;
            // 나머지도 검사했는데, 유효하면 최종 정답
            // 나머지에서 에러나면 0으로 다시 바꾸고 다음 0을 검사
            if (checkArray(array)){
              return true;
            } else {
               array[rowIndex][colIndex] = 0;
            }
          }
        }
        return false;
      }
    }
  }
  return true;
}

function solution(input) {
  const array = change2DArray(input);
  if(checkArray(array)) {
    array.forEach(row => console.log(row.join('')));
  }
}

const input = `103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107`;

solution(input);

* 백준답안으로 바꿔야함

시간 복잡도

change2DArray는 항상 고정된 크기이므로 시간복잡도는 O(1)

isValid는 각각의 for 루프가 최대 9번 반복하므로 O(9)로 O(1)로 간주

checkArray는 최악인 경우 9^91의 재귀 호출이발생할 수 있지만 스도쿠의 경우 비어있는 칸이 적기 때문에 보통의 경우 O(1)에 가까움 

백트래킹

해결책을 찾기 위해 후보군을 탐색하다가 해당 후보군이 해결책의 조건을 만족하지 않으면, 이전 단계로 돌아가서 다른 후보군을 탐색하는 방법

주로 깊이 우선 탐색DFS과 결합하여 문제를 해결

DFS 진행중, 조건에 만족하지 않는 경우를 빠르게 탐지하고 이전 단계로 돌아감

일반적으로 재귀적으로 구현하며, 유효성을 만족하지 못하는 경우를 조기에 제거하는데 의