BOJ_14620 꽃길

• TOC {:toc}

이 글은 백준 온라인 저지의 14620번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.08.14 (Python)

N = int(input())
G = [list(map(int, input().split())) for _ in range(N)]
P = [[0] * N for _ in range(N)]
MAX = 200 * 15 + 1
ans = MAX


def ck(flowers):
    res = 0

    for i in range(3):
        my, mx = divmod(flowers[i], N)
        ny, nx = divmod(flowers[i - 1], N)
        if mx == 0 or mx == N - 1 or my == 0 or my == N - 1:
            return MAX
        if abs(my - ny) + abs(mx - nx) <= 2:
            return MAX
        else:
            res += P[my][mx]

    return res


dx = [0, -1, 0, 1, 0]
dy = [0, 0, 1, 0, -1]

for i in range(1, N - 1):
    for j in range(1, N - 1):
        for k in range(5):
            P[i][j] += G[i + dy[k]][j + dx[k]]

for i in range(N * N):
    for j in range(i + 1, N * N):
        for k in range(j + 1, N * N):
            ans = min(ans, ck([i, j, k]))

print(ans)

아이디어 & 풀이

완전 탐색을 이용해 세 화단의 조합을 순회하면서 화단 가격 합의 최솟값을 찾는다.

• 원래 세 쌍의 x, y 좌표를 탐색해야 하기 때문에 6중 반복문을 사용해야 하지만 각 칸에 순서대로 번호를 붙이면 3중 반복문으로 해결할 수 있다.

• 예를 들어 6 x 6 화단의 좌표는 다음 두 방식으로 나타낼 수 있다.

  (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)   00 01 02 03 04 05
  (1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5)   06 07 08 09 10 11
  (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5)   12 13 14 15 16 17
  (3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5)   18 19 20 21 22 23
  (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5)   24 25 26 27 28 29
  (5, 0) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5)   30 31 32 33 34 35
  

• 즉 x와 y를 별개로 순회하지 않고, 0부터 N * N까지 한 번에 순회하면 된다.

함수를 만들어 선택한 세 화단에 꽃이 시들지 않게 씨앗을 심을 수 있는지 확인하고, 가능하다면 세 화단 가격의 합을 반환한다.

• 반환받은 값을 min으로 기존값과 비교해 최솟값을 찾는다.
• 꽃이 시들지 않는 조건을 만족하지 못하면 화단 가격의 최댓값보다 큰 수인 MAX를 반환한다.
  • MAX = 화단 한 개의 최대 가격(200) * 화단의 개수 (15) + 1
  • 그래야 min(ans, ck([i, j, k])) 결과에 영향을 미치지 않는다.

함수 내부에서 꽃잎이 시들지 않는 조건인지는 다음과 같이 확인한다.

• 우선 G는 이차원 리스트로 구현되어있기 때문에 인자로 받은 화단 번호를 이차원 좌표(x, y)로 나타내야 한다.
  • 받은 번호를 N으로 나눈 몫과 나머지를 구하면 된다. 행이 몫, 열이 나머지이다.
  • e.g., 7 → 7 // 6은 1, 7 % 6은 1로 (1, 1)
• 꽃잎 일부가 화단 밖으로 나가 시들기 때문에 화단 테두리에는 씨앗을 심을 수 없다.
  • 씨앗의 x 인덱스나 y 인덱스가 0이나 N - 1이면 씨앗을 심을 수 없고 MAX를 반환한다.
• 씨앗을 심었을 때 다른 씨앗의 꽃잎과 닿으면 안 된다.

  • 임의의 지점에 씨앗을 심었을 때 다른 씨앗을 심지 못하는 영역은 다음과 같다.

    | | |X| | | | |  S: 씨앗 
    | |X|O|X| | | |  O: 꽃잎 
    |X|O|S|O|X| | |  X: 씨앗을 심지 못하는 영역
    | |X|O|X| | | |
    | | |X| | | | |
    | | | | | | | |
    

  • 꽃잎 영역을 포함해서 씨앗에서 x, y 좌표를 합쳐 두 칸 안쪽(e.g., x: 2칸, y: 0칸 / x: 1칸, y: 1칸)에는 씨앗을 심을 수 없다.

  • 즉, 좌표 (x1, y1)에 씨앗을 심었으면 다른 씨앗의 좌표 (x2, y2)는 다음을 만족해야 한다: abs(x1 - x2) + abs(y1 - y2) <= 2

위 두 경우에 해당하지 않으면 세 씨앗 위치에 따른 화단 가격의 합을 더해 반환한다.

• 각 씨앗 위치에 따라 필요한 화단 가격의 합은 미리 계산해둔다.
  • 현재 화단과 그 상하좌우의 화단 가격을 모두 더하면 된다.
  • 현재 화단을 포함해야 하므로 dx, dy 리스트에 (0, 0)를 추가해준다.

디버그

• MAX를 화단 5개를 기준으로 잡아서 틀렸다. 구매해야 하는 화단은 총 15개다.

피드백

2023.02.20 (JS)

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

const [stringN, ...lines] = input;
const N = parseInt(stringN);
const MAX_PRICE = 200;

function isValid(indices) {
    for (let i = 0; i < 3; i += 1) {
        const x1 = indices[i] % N;
        const y1 = parseInt(indices[i] / N);
        const x2 = indices[(i + 1) % 3] % N;
        const y2 = parseInt(indices[(i + 1) % 3] / N);

        if (!x1 || !y1 || x1 === N - 1 || y1 === N - 1) {
            return false;
        }
        if (Math.abs(x1 - x2) + Math.abs(y1 - y2) <= 2) {
            return false;
        }
    }
    return true;
}

function main() {
    const field = [];
    const fieldSize = N * N;
    lines.forEach((line) => {
        const rows = line.split(" ").map((n) => parseInt(n));
        field.push(...rows);
    });

    const price = new Array(fieldSize).fill(0);
    for (let i = 1; i < N - 1; i += 1) {
        for (let j = 1; j < N - 1; j += 1) {
            const idx = i * N + j;
            price[idx] = field[idx] + field[idx - 1] + field[idx + 1] + field[idx + N] + field[idx - N];
        }
    }

    let minPrice = MAX_PRICE * fieldSize;
    for (let i = 0; i < fieldSize - 1; i += 1) {
        for (let j = i + 1; j < fieldSize - 1; j += 1) {
            for (let k = j + 1; k < fieldSize - 1; k += 1) {
                if (isValid([i, j, k])) {
                    minPrice = Math.min(price[i] + price[j] + price[k], minPrice);
                }
            }
        }
    }

    return minPrice;
}

console.log(main());

피드백

• j는 i + 1에서 k는 j + 1에서 시작하자.
• i, j, k를 x, y로 분리해주는 것을 main 내의 탐색 과정에서 했는데 그것보다 isValid 안에서 하는 게 효율적이다.

참고 답안

# 풀이 1-1
import sys
from itertools import combinations

input = sys.stdin.readline

N = int(input())
F = [[*map(int, input().split())] for _ in range(N)]
ds = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]
v = {1, 2, N, N + 1, N - 1, 2 * N}


def ck(a, b, c):
    if abs(a - b) in v or abs(b - c) in v or abs(c - a) in v:
        return False
    return True


I = []
P = {}

for x in range(1, N - 1):
    for y in range(1, N - 1):
        res = 0
        for dx, dy in ds:
            nx, ny = x + dx, y + dy
            res += F[nx][ny]

        i = N * x + y
        P[i] = res
        I.append(i)

ans = min(sum(P[f] for f in flowers) for flowers in combinations(I, 3) if ck(*flowers))
print(ans)

# 풀이 1-2
import sys
input = sys.stdin.readline

N = int(input())
G = [list(map(int, input().split())) for _ in range(N)]
MAX = 200 * 15 + 1
ans = MAX

dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

def ck(flowers):
    P = set([])

    for f in flowers:
        y, x = divmod(f, N)
        if x == 0 or x == N - 1 or y == 0 or y == N - 1:
            return MAX
        for i in range(5):
            P.add((y + dy[i], x + dx[i]))
    if len(P) != 15:
        return MAX

    return sum([G[y][x] for y, x in P])
        
for i in range(N * N):
    for j in range(i + 1, N * N):
        for k in range(j + 1, N * N):
            ans = min(ans, ck([i, j, k]))

print(ans)

아이디어 & 풀이

전체적인 진행은 비슷하지만, 꽃잎이 시들지 않는 조건을 확인하는 방식이 다르다.

• 풀이 1-1
  • 테두리 안쪽의 화단만 순회하면서 그 인덱스는 리스트 I에 상하좌우를 포함한 화단의 비용은 딕셔너리 P에 저장한다.
  • ck 함수로 I 중 세 개를 선택한 조합에 대해서 꽃을 겹치지 않게 심을 수 있는지 확인한다.
    • 두 번호를 x, y 좌표로 바꾸지 않고 두 번호 자체의 차이를 계산한다.
    • 두 수의 차이가 1, 2, N, N + 1, N - 1, 2 * N 안에 있으면 두 꽃이 겹치게 된다.
  • ck의 반환 값이 True인 원소에 대해서 세 화단의 가격의 합을 모두 구한 뒤 그 최솟값을 출력한다.
• 풀이 1-2
  • 구매해야 할 화단을 담는 집합 P를 만든다.
  • 선택한 세 지점에 꽃을 심기 위해 구매해야 하는(선택 지점 및 그 상하좌우) 화단을 P에 추가한다.
  • 꽃잎이 겹치지 않으려면 구매해야 하는 화단이 모두 달라야 하므로 P의 원소의 개수가 15개여야 한다.
  • len(P)가 15인지 확인해 아니면 MAX를 반환한다.
  • len(P)가 15이면 P의 모든 원소의 합을 반환한다.