[실버 2] 백준 14620 - 꽃길 (파이썬)

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

풀이

1. 모든 좌표 중 3개를 조합으로 고른다.
2. 각 조합마다 꽃이 겹치지 않는지, 범위를 벗어나지 않는지 확인한다.
3. 문제가 없다면 그 조합의 총 비용을 계산하고 최소값을 갱신한다.

from itertools import combinations

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

• N은 격자 크기.
• A는 각 칸의 비용을 저장한 2차원 배열.

coordinates = [(i, j) for i in range(N) for j in range(N)]

• 모든 좌표 (i, j)를 저장.

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
answer = 1e9

• 상하좌우 방향 설정.
• answer는 최소값 초기화.

for combination in combinations(coordinates, 3) :

• 좌표 중 3개를 뽑는 모든 조합을 순회.

blossom = set()
bad = False
cost = 0

• blossom: 사용된 좌표 저장
• bad: 꽃이 겹치거나 격자 벗어나면 True
• cost: 현재 조합의 비용 합계

for (r, c) in combination :
    if (r, c) in blossom :
        bad = True
    blossom.add((r, c))
    cost += A[r][c]

• 중심 위치 이미 사용됐으면 bad
• 비용에 중심 위치 추가

for i in range(4) :
    nr, nc = r + dr[i], c + dc[i]
    if nr < 0 or N <= nr or nc < 0 or N <= nc :
        bad = True
        break
    if (nr, nc) in blossom :
        bad = True
        break
    blossom.add((nr, nc))
    cost += A[nr][nc]

• 꽃잎 4방향을 탐색
• 범위 벗어나거나 겹치면 bad
• 안 겹치면 좌표를 blossom에 추가하고 비용 누적

if not bad :
    answer = min(answer, cost)

• 문제 없는 조합이면 최소 비용 갱신

코드

# 백준 14620 - 꽃길
# 분류 : 브루트포스

from itertools import combinations

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

coordinates = [(i, j) for i in range(N) for j in range(N)]

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
answer = 1e9

for combination in combinations(coordinates, 3) :
    blossom = set()
    bad = False
    cost = 0
    for (r, c) in combination :
        if (r, c) in blossom :
            bad = True
        blossom.add((r, c))
        cost += A[r][c]
        for i in range(4) :
            nr, nc = r + dr[i], c + dc[i]
            if nr < 0 or N <= nr or nc < 0 or N <= nc :
                bad = True
                break
            if (nr, nc) in blossom :
                bad = True
                break
            blossom.add((nr, nc))
            cost += A[nr][nc]
    
    if not bad :
        answer = min(answer, cost)

print(answer)