2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

문제

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

꽃을 심기 위한 최소 비용을 출력한다.

예제 입력

6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1

예제 출력

12

내가 했던 풀이 방법

1. flower 배열을 N×N으로 두고 0으로 채운다. 이 배열에는 해당 위치에 씨앗을 심었을 때 발생하는 비용이 저장된다.
2. 1부터 N-2까지 해당 위치에 씨앗을 심었을 때 발생하는 비용을 저장한다. 꽃은 영역을 넘어갈 수 없으므로 index 범위에 유의한다.
3. 첫 번째 꽃이 위치하는 (씨앗을 심은) 곳에 가격을 cost1에 저장한다. 두 번째 꽃이 x1과 만나지 않으면 cost2에 저장한다. 세 번째 꽃이 x1, x2와 모두 만나지 않으면 cost3에 저장한다. 그 값의 합을 totalCost에 저장하고 minCost보다 작을 경우, minCost 값을 바꿔준다. (이때 해당 꽃이 만나지 않는지 파악하기 위해 isOverlap 함수를 이용했다. 해당 함수에서는 두 꽃이 영역 중 겹치는 곳이 하나라도 있을 경우, true를 return 해준다.)

코드

const fs = require('fs');
let [N, ...prices] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
let directions = [
  [0, 0],
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

for (let i = 0; i < N; i++) {
  prices[i] = prices[i].trim().split(' ').map(Number);
}

function isOverlap(x1, y1, x2, y2) {
  for (let [dx1, dy1] of directions) {
    for (let [dx2, dy2] of directions) {
      if (x1 + dx1 === x2 + dx2 && y1 + dy1 === y2 + dy2) {
        return true;
      }
    }
  }
  return false;
}

let minCost = Infinity;
let flower = Array.from({ length: N }, () => Array(N).fill(0));
for (let i = 1; i < N - 1; i++) {
  for (let j = 1; j < N - 1; j++) {
    let cost = 0;
    for (let [dx, dy] of directions) {
      cost += prices[i + dx][j + dy];
    }
    flower[i][j] = cost;
  }
}

for (let x1 = 1; x1 < N - 1; x1++) {
  for (let y1 = 1; y1 < N - 1; y1++) {
    let cost1 = flower[x1][y1];

    for (let x2 = 1; x2 < N - 1; x2++) {
      for (let y2 = 1; y2 < N - 1; y2++) {
        if (isOverlap(x1, y1, x2, y2)) continue;
        let cost2 = flower[x2][y2];

        for (let x3 = 1; x3 < N - 1; x3++) {
          for (let y3 = 1; y3 < N - 1; y3++) {
            if (isOverlap(x1, y1, x3, y3) || isOverlap(x2, y2, x3, y3)) continue;
            let cost3 = flower[x3][y3];

            let totalCost = cost1 + cost2 + cost3;
            if (totalCost < minCost) {
              minCost = totalCost;
            }
          }
        }
      }
    }
  }
}

console.log(minCost);

회고

해당 위치에 꽃이 겹치는지 확인하는 방법을 떠올리는 게 생각보다 쉽지 않았는데 direction 배열에 꽃이 자라는 범위를 모두 저장해주면 해결이 금방됐다. 가끔 direction을 저장해두는 게 편할 때가 많은데 이런 식의 문제들이 나오면 direction을 사용하는 걸 습관화해야겠다.