문제 96. 넓은 텃밭 만들기

 

 

 

예림이는 귀농을 해서 밭농사를 시작하기로 마음을 먹었다. 텃밭에 큰 바위들은 제거하지 못하여 다음과 같은 규칙들을 정하였다.

 

1. 바위를(바위는 '1'로 표기) 피해텃밭을 만들되 정사각형 모양으로 텃밭을 만듬
2. 텃밭은 가장 넓은 텃밭 1개만 만듦, 그 크기를 반환.
3. 만든 텃밭은 모두 '#' 으로 처리

 

가장 넓게 만들수 있는 텃밭의 길이와 텃밭을 출력하시오

// 입력
0 0 0 0 0
0 1 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0

// 출력
3 x 3

0 0 # # #
0 1 # # #
0 1 # # #
0 0 1 0 0
0 0 0 1 0


// 입력
0 0 0 1 0
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 1 0

// 출력
2 x 2

# # 0 1 0
# # 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 1 0


/* **********문제********** */
const 텃밭 = []; //입력받은 텃밭 리스트
let 가꾼텃밭 = []; //텃밭을 가꾼 후 저장된 리스트

// 코드작성

console.log(가꾼텃밭)

 

 

미리 생각해 봐야할 것

재귀함수와 다이나믹 프로그래밍(Memoization)을 먼저 알고 문제에 적용해보자

• 다음과 같은 재귀함수가 있다

function fn(n) {
  if (n === 1 || n === 2) {
    return 1;
  } else {
    return fn(n - 1) + fn(n - 2);
    // fn(6)
    // fn(5) + fn(4)
    // fn(4) + fn(3) + fn(3) + fn(2)
    // fn(3) + fn(2) + fn(2) + fn(1) + fn(2) + fn(1) + fn(2)
    // fn(2) + fn(1) + fn(2) + fn(2) + fn(1) + fn(2) + fn(1) + fn(2)
  }
}

console.log(fn(6));

 

 

 

같은 함수가 반복해서 실행이 되고 있음 -> 비효율적 -> 그렇다면 memoization 을 활용하자 !

• memoization 기법
  : 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.

let n = 6;
let memory = Array(n + 1).fill(0); //[ 0, 0, 0, 0, 0, 0, 0 ]

function fn(n) {
  if (n === 1 || n === 2) {
    memory[n] = 1;
    return 1;
  } else if (memory[n] !== 0) {
    // 값이 들어가 있을 때
    return memory[n];
  } else {
    memory[n] = fn(n - 1) + fn(n - 2);
    console.log(memory[n]);
    return memory[n];
  }
}

// 변화되는 양상

// [0, 0, 0, 0, 0, 0, fn(5) + fn(4)]
// [0, 0, 0, 0, 0, fn(4) + fn(3), fn(5) + fn(4)]
// [0, 0, 0, 0, fn(3) + fn(2), fn(4) + fn(3), fn(5) + fn(4)]
// [0, 0, 0, 0, fn(3) + fn(2), fn(4) + fn(3), fn(5) + fn(4)]
// [0, 0, 0, fn(2) + fn(1), fn(3) + fn(2), fn(4) + fn(3), fn(5) + fn(4)]
// [0, 0, 1, fn(2) + fn(1), fn(3) + fn(2), fn(4) + fn(3), fn(5) + fn(4)]
// [0, 1, 1, fn(2) + fn(1), fn(3) + fn(2), fn(4) + fn(3), fn(5) + fn(4)]
// [0, 1, 1, 2, fn(3) + fn(2), fn(4) + fn(3), fn(5) + fn(4)]
// [0, 1, 1, 2, 3, 5, 8]


// 2
// 3
// 5
// 8

console.log(fn(n)); // 8

 

 

 

답

let 텃밭 = `0 0 0 0 0
0 1 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0`
  .replace(/1/g, "!")
  .replace(/0/g, "1")
  .replace(/!/g, "0")
  .split("\n");

console.log(텃밭);

let 역전텃밭 = [];
for (let row of 텃밭) {
  역전텃밭.push(row.split(" "));
}

function sol(역전텃밭) {
  const 높이 = 역전텃밭.length;
  const 넓이 = 역전텃밭[0].length;
  let max = 0;
  let posx = 0;
  let posy = 0;

  for (let i = 0; i < 높이; i++) {
    for (let j = 0; j < 넓이; j++) {
      역전텃밭[i][j] = parseInt(역전텃밭[i][j], 10);
    }
  }
  for (let i = 1; i < 높이; i++) {
    for (let j = 1; j < 넓이; j++) {
      if (역전텃밭[i][j] == 1) {
        let min;
        //좌측원소의 값이 가장 작을 경우
        if (역전텃밭[i - 1][j] >= 역전텃밭[i][j - 1]) {
          min = 역전텃밭[i][j - 1];

          // 윗측원소의 값이 가장 작을 경우
        } else if (역전텃밭[i - 1][j] <= 역전텃밭[i][j - 1]) {
          min = 역전텃밭[i - 1][j];
        }

        // 대각선 원소의 값이 가장 작은 경우
        if (min >= 역전텃밭[i - 1][j - 1]) {
          min = 역전텃밭[i - 1][j - 1];
        }
        // 현재 기준점이 그릴수 없는 가장 큰 정사각형의 한변의 길이
        역전텃밭[i][j] = min + 1;

        // 텃밭 배열에서 가장 큰 숫자 찾기
        if (max < 역전텃밭[i][j]) {
          max = 역전텃밭[i][j];
          posx = j;
          posy = i;
        }
      }
    }
  }
  // 밭을 # 으로 표기
  for (let i = posy - (max - 1); i < posy + 1; i++) {
    for (let j = posx - (max - 1); j < posx + 1; j++) {
      역전텃밭[i][j] = "#";
    }
  }
  // 숫자를 다시 0과 1로 표기
  for (let i = 0; i < 높이; i++) {
    for (let j = 0; j < 넓이; j++) {
      if (역전텃밭[i][j] >= 1) {
        역전텃밭[i][j] = 0;
      } else if (역전텃밭[i][j] == 0) {
        역전텃밭[i][j] = 1;
      }
    }
  }
  // 밭 출력
  for (let i of 역전텃밭) {
    console.log(i);
  }
  // 크기 출력
  console.log(`${max} x ${max}`);
}

sol(역전텃밭);